I give all credit of this guide to Kuroe, as she was the one who did the leveling and wrote about it.
-------------
Ok, after leveling for the second time, just some generalizations about Cata leveling that people should be aware of (in no particular order, and I'll add more as I think of it):
1. First of all, this is not like Wrath leveling - so don't expect it to be. You should not plan on doing orange/red quests, or skipping to zones that you have no business in. If you skip a zone other than a starter zone, you will probably find yourself undergeared for the next zone.
2. It seems like leveling from 80-85 PROBABLY will be faster than 70-80. You may be done in 1-3 days, depending on game time and questing tolerance threshold.
3. Quests are extremely linear. Meaning - 99% of the quests simply cannot be skipped. In some cases this sucks (see: "kill x named mob" and you find yourself waiting around with 10 other people trying to snipe the tag on it), but in other cases it works out better, as there is a lot of apparent phasing to different steps of quests. This also means that at most you will probably only have 1-4 quests in your log for a specific zone at a time, so don't expect to pick up 5-7 quests and then turn them all in at once - that simply won't happen this time around.
4. There are a lot of "vehicle" quests. Get used to it, you can't easily skip most of them. (You CAN, however, skip the "second" Twilight Portal in Hyjal... and I'd recommend it, as it's pretty annoying (not difficult, but annoying). Go back and do it after you hit 85 - it gives an achievement and a pet.)
5. Your level 80 halion/icc heroic epics will NOT last you to 85. They won't even last you to 84. Do not hesitate to replace your gear, break your set bonuses, and try out some new pieces. You won't even be able to queue for NORMAL instances if you do not, as they have average ilvl requirements. (Example: Vortex Pinnacle in Uldum has a ilvl 305 prereq to even enter the normal version.)
6. There are SEVERAL cut scenes while questing. Most of them you can skip (hit ESC and confirm you wish to skip it), but there are a few you can not. If you skip them you will obviously miss part of the story behind your quest chain.
7. You can NOT use your seahorse anywhere other than Vash'jir. Also, if you are standing on the ocean floor you will not be able to mount it - so hop up a little bit and you will be able to.
8. You can drink/eat/run on the ocean floor.
9. Quests that send you to new zones from Orgrimmar signboards become available as you level. Follow the directions in the quest for how to get to your new zone. Excluding Uldum, most of these quests give you "shortcuts" to the new area.
Level 80 = Hero's Call: Hyjal! and Hero's Call: Vash'jir!
Level 82 = Hero's Call: The Maelstrom! (Deepholm)
Level 83 = Hero's Call: Uldum! - Note: There is no "easy" port to Uldum, despite what the quest says (unless they change it before release). If this is still true come Cata release, you will want to either find a person that has a Dalaran port (since you should have your hearth set to Stormwind), or you will want to use the Ring of the Kirin Tor (if you bought it) to take the Caverns of Time portal to Tanaris, and then fly to Thistleshrub Valley.
Level 84(?) = Hero's Call: Twilight Highlands! - Note: This quest starts a short chain of quests within Stormwind itself, and then ends in an NPC "flying" (essentially porting) you to Twilight Highlands.
After you do these quests and enter the zones for the first time, there will be portals to these zones directly from The Earthen Shrine in Stormwind. (The small island area in the northeast of the zone map, surrounded by a pond.)
10. Mobs hit extremely hard, and have a lot of HP. After Vash'jir/Hyjal, you will not want to be pulling more than 1-2 mobs at a time.
11. As you level, if you are wearing the same level 80 gear your stats will obviously diminish drastically. Essentially this means you will be doing less damage and healing for less at 81 than you were at 80, even if all your gear remains the same - so don't be surprised. (This isn't new, obviously - but it's important to remember, and it's far more noticeable this expansion than it was last.)
12. Casters will need to bring water (and/or food). Melee will want to bring food. Your self healing and mana regeneration will not mean much beyond level 82. (Example: I have to drink. I'm a shadow priest with dispersion, replenishment, shadowfiend... and I have to drink.)
13. If you have NPCs disappear following a cut scene, relog and they should show up again.
14. This time around, you will have to "discover" instance entrances before you can queue for them. I don't personally think that instancing will be an efficient way to level - but if you want to try to do one random a day ("try" being the key word - the instances are supposedly not as easy this time around, and your "random" group may and probably will be completely unfamiliar with the mechanics) it gives ~80-100k xp. Given, at the point where you're getting 100k xp for an instance, each quest is worth about 44k - so it's probably not worth it.
15. Instance quests are located inside the instances now, although in some cases there may be a chain that "sends" you there.
16. There is a new "Ring of Blood" is called "Crucible of Carnage" and it is located in Twilight Highlands and is available at level 84.
17. Azerothian flying can be trained from either an NPC near the flight master in Org (use the elevator), or at the flight trainer in Dalaran (but if you're in Dalaran when Dec 7 12 am PST comes around - you're doin it wrong.)
18. Don't set your hearth in new zones, leave it at Orgrimmar - else it will be quite a flight to get you back to town.
19. Don't try to train every level, and consider if you will "need" the spell while you are leveling or not - there are only new spells at 81, 83, 85. Spell ranks automatically go up as you gain levels (and so do their mana costs) - so there is really no need to go to town specifically to train unless you really need that spell.