By the time you read this, Mists of Pandaria should be out and playable in Europe (coming soon to the US), and there's probably even a few of you who will have hit level 86 or 87. With the new talent and specialization system, I expect figuring out how to level will be easier than ever, if only because it's a lot more difficult to go wrong. Still, there's a few recommendations to make that may help you hit level 90 just a bit faster, and we'll go ahead and dispense some of that advice today. Note that all advice here is for leveling only, and may not apply to end game dungeon running or raiding.
Choosing your leveling spec
I would recommend you choose either two-handed frost or blood as your leveling spec. Blood is strong enough and has enough self-healing and emergency defense tools that will probably never die. That said, your DPS won't be as high as you might like. Frost will allow you to kill things faster but still gives you some decent survivability options in the form of Death Strike and, if you talent in to it, the Lichborne heal trick. If you do level as blood, make sure you are either queuing for dungeons as a tank, or have a secondary frost or unholy spec ready to switch to when you DPS a dungeon. Blood is still not great DPS, and your dungeon group will need better than what you can put out as blood.
While unholy can technically do the Lichborne heal trick too, it suffers from having Death Strike completely throw off its damage rotation, and it doesn't have as much clutch burst damage as unholy and frost. It also does relatively more damage via disease, and you'll be killing mobs too fast to make applying diseases worth it. You do get the advantage of the speed boost from Unholy Presence, which is a plus, but it'll still be much more challenging to level.
You won't really have to straight up pull off a picture perfect damage rotation to level. You'll mostly want to focus on burst damage. That means putting up diseases isn't as important. If you have Unholy Blight or Outbreak up, use it, if not, no sweat. Frost will probably want to throw out a Howling Blast for some extra frost damage and physical vulnerability, of course. Other than that, focus on getting your most damaging strikes up. That means Obliterate for two-handed frost, while blood should focus on spamming Heart Strike after using Death Strike to make unholy runes. If you're AoEing a lot of mobs, you'll mostly focus on spamming Howling Blast or Blood Boil, depending on your spec.
You will also want to use Death Grip smartly. If you can use Death Grip to avoid running to another mob, do it. Leveling is the time you use Death Grip with wild abandon. The presence you use will be the one with the same name as your chosen spec.
For the most part, your gear choices are easy-peasy. Mists of Pandaria primarily offers gear rewards based on your spec, so just take the strength gear, and you'll be good to go. If you're given a choice, blood should go for mastery and parry gear, while frost should focus on haste and mastery gear and unholy should grab haste and critical strike gear.
For the most part, you shouldn't worry about enchanting or gemming leveling gear, as you'll replace it too quickly for the money to be worth the relatively marginal power gain. One exception is Runeforging. It costs us nothing, so don't be afraid to cast Death Gate and apply Rune of the Fallen Crusader. That extra strength and healing is nothing to sneeze at.
The well glyphed death knight
While glyphs aren't really set up for extra DPS these days, some of them offer some key help for the leveling death knight. Glyph of Dark Succor is just the thing for chain-pulling quest mobs, whether you're blood or frost. If you're down a bit after killing a mob, don't sit and drink, pull the next one and apply death strike. Glyph of Unholy Command is just the thing for chain-pulling quest mobs. Grab it. I would also recommend Glyph of Path of Frost. Since you won't be able to fly until you hit level 90, having some insurance against long drops while you're exploring or heading to your next questing area will be useful..
Talents: Choose 'em and use 'em
While talent choices are a lot more free form this time around, there are some that will provide you will superior utility for the leveling process, but only if you use them correctly.
At Tier 1, you'll probably want to choose between either Roiling Blood or Unholy Blight. Roiling Blood may be useful for chain pulls as a blood or unholy death knight, since you can do damage and spread diseases while wasting as few runes as possible, but Unholy Blight provides the most versatility as a clutch disease application method when you can't spare the runes for other methods.
At Tier 2, Go for Lichborne. You'll want the Lichborne heal trick. Be sure to set up a macro like so:
/cast [target=player] Death Coil
With this macro, you can press a single button over and over. The first press will cast Lichborne, and every other press after will heal you with Death Coil. If you can, hold off on using it until you have a lot of runic power saved up.
At Tier 3, go for Death's Advance. Having some extra speed to chase down monster or run between monsters means you level that much faster.
At Tier 4, I'd recommend Death Pact. It gives you the most healing bang for your buck. Death Siphon might also be useful, but, especially while leveling, it'll be less healing, and you'll give up a little damage while you use it. Still, it's less damage given up than Death Pact.
At Tier 5, you probably want to go for something simple. Playing rune tetris just isn't worth it for the leveling game. You can choose any of the 3 choices, really, but gaming them isn't worth your time. If you're looking to macro Blood Tap, try the following macro:
#showtooltip Rune Strike
/cast Blood Tap
/cast Rune Strike
Rune Strike, of course, is for blood death knights only. Replace Rune Strike with Frost Strike for frost or Death Coil for unholy. Then, use that macro as your default button press whenever you're spending runic power. Since Blood Tap isn't on the global cooldown, you'll use it automatically, no mess, no fuss.
Note that above I originally had the tier names listed by their traditional levels, that is, 15, 30, 45, 60, and 75. Technically, however, death knights are slightly different in that we start at level 55 and get our talents over the next couple levels. As this is technically a level 85-90 leveling guide, it may not make one difference, but I have renamed the levels to "tiers" in order to avoid any confusion.
Learn the ropes of endgame play with WoW Insider's DK 101 guide. Make yourself invaluable to your raid group with Mind Freeze and other interrupts, gear up with pre-heroic DPS gear or pre-heroic tank gear, and plot your path to tier 11/valor point DPS gear.