You've actually taken the major first step in that you are thinking about it this far out.
Facility/building requirements is one step and it sounds like you probably have a handle on that. If you move into a pre-existing facility, what is the state of the existing data/voice infrastructure? Who will be handling the installation/renovation of the data/voice infrastructure (you and your team, or will it be outsourced)?
You need to think about services (phone/Internet connectivity) and what type of lead time the vendors of these services will require for installation. Included in this is whether your present vendors for these services can still support you in the new location or whether you must find new vendors. Do you want to takethe opportunity to upgrade services (maybe move from a leased frame relay or ISDN circuit to a broadband circuit if available at your new location)?
What is the distance between the old and new location? Who will handle the physical move of computers/network/phone equipment? Is the distance such that the move can take place over night or over a weekend? Are there any business-critical processes than won't tolerate ANY down-time? Will you need to provide any services concurrently at both the old and new facility?
I'll add more stuff as I think about it (I've been through this a couple of times).