Wondering what to do when Cataclysm hits? Regardless of your intentions, the first thing you will want to do - unless levelling a new toon - is to learn to fly in Azeroth. And unless you intend to farm reagents, you will probably want to learn Illustrious of all your professions, grab Archaeology if so inclined, and then head to one of the two starting zones.
So where do you want to be when the switch gets flipped? Well, for Alliance, Stormwind is a good start, as you can do everything there. For Horde it is Orgrimmar. Grab your Flight Master's License, run a circuit, picking up all of your skills and then head to the relevant NPC to be on your way to your zone of choice.
Unfortunately, I don't play Horde, so I'm going to only focus on helping Alliance get to where they need to be to optimise their first few minutes of playing. Sorry, Hordies!
Here is a summary of all the trainers and relevant NPCs to get started. I simply collected data straight from Wowhead and consolidated it for easy reading:
Flight Master's License
Flying Trainer - Bralla Cloudwing (70.8 73.2). This is where you want to be at 12.01am on the 7th of December, or logged out at if unable to be playing when Cataclysm hits.
Gathering Profession Trainers
Herbalism Trainer - Tannysa (54.6 83.6).
Mining Trainer - Gelman Stonehand (59.6 37.6).
Skinning Trainer - Maris Granger (72.7 62.0).
Crafting Profession Trainers
Alchemy Trainer - Lilyssia Nightbreeze (55.6 85.9).
Blacksmithing Trainer - Therum Deepforge (63.8 37.2).
Enchanting Trainer - Lucan Cordell (53.0 74.3).
Engineering Trainer - Lilliam Sparkspindle (62.8 32.2).
Inscription Trainer - Catarina Stanford (49.8 74.2).
Jewelcrafting Trainer - Theresa Denman (63.5 61.5).
Leatherworking Trainer - Simon Tanner (71.8 62.9).
Tailoring Trainer - Georgio Bolero (53.2 81.7).
Secondary Profession Trainers
Archaeology Trainer - None other than Harrison Jones (85.7 25.9).
Cooking Trainer - Stephen Ryback (78.1 53.2).
First Aid Trainer - Shaina Fuller (52.9 44.9).
Fishing Trainer - Arnold Leland (55.1 69.5).
The Starting Zones
Quest to start in Mt Hyjal - Hero's Call: Mt Hyjal! Obtainable from Hero's Board (62.3 30.1 and 63.0 71.8). Ends in Moonglade. Handed in at Cenarion Emissary Jademoon (83.0 28.8).
Quest to Start in Vashj'ir - A Personal Summons. Automatically given to you when you enter Stormwind. Ends at Naraat the Earthspeaker (74.6 19.3).
Following is a map to see the locations of all trainers and key points to help you plot your path and be on your way fully prepared.
Tip: Remember to have all necessary bagspace, levelling reagents and anything else ready before Cataclysm goes live so that you aren't wasting time flying to the bank or the auction house - even though they are both very cool now.
I hope that this is insightful and helpful to people.
As a final note: personally, I am going to level Archaeology on my main for a bit before heading to my chosen levelling zone. It will give me a chance to both check out the changed zones that I haven't managed to see pre-Cata as well as eventually level the skill up for the end-game zones. I'm sure that others will be inclined this way too. Good luck, whatever you decide to do!