What should I do if the professor I intended to work with has moved to a different school?
Yeah, this happens. :(

I would recommend applying to school Z during your first year at school X. This would be very natural under the circumstances, and nobody (in particular, not those at school X) will think less of you for it.

Further, I'd recommend:


E-mail and ask Prof. Y if he'd be willing to vouch for you with the graduate admissions committee at school Z. 
Simultaneously apply to a couple of other programs that might be more suitable for you than school X. This goes especially if Z is substantially more selective than X, so you are far from sure that you'll get in.
Kick ass in your first year at X. This will keep you sharp, enable you to get a letter of support from someone at X, and better prepare you for the program at Z if you go.
Keep in mind that you might not get into Z, or you might find a research area you like at X and decide you prefer to stay. (Another reason to kick ass in your first year at X.)


Good luck to you!