What? A leveling guide from 71-80? Nine months after Wrath of the Lich King has been released? Well, sure. Obviously this won't be geared towards players who use Paladins as their main. One of these days, maybe next week, we'll probably get around to talking about Crusader's Coliseum and the Trial of the Crusader. Then again, didn't you just one-shot all those bosses last week? Anyway, just for this week we'll pick up where we left off when we last hit Level 70 (or so). The excitement seems to be pointing towards the next batch of content - from reawakened black dragons, to the inevitable opening of Icecrown, and of course, the advent of a new expansion.
Actually, there couldn't be a better time to dust off that Paladin alt (probably once your main, who knows?) because... well, what class would you really want to bring to a face off with the freaking Lich King? A class that knows how to lay the smackdown with the freaking Light, that's who! Besides, when they finally allow paid race changes some months after the next expansion (come on, you didn't really think they'd let you pay to switch to a max level Goblin or Worgen right off the bat, did you?), wouldn't you want a high level Paladin standing at the ready to be transformed into a badass werewolf? Alright, I'm just teasing you. It probably won't happen, but if it did, at least you wouldn't be kicking yourself in the head. Ok, so, you're Level 70 and sailing off to Northrend. Let's hit it.
First things first
I mentioned this was the perfect time to write this guide -- aside from the electric monkey prods of our head honchos telling us to update or complete our leveling guides, that is -- because Patch 3.2 made it infinitely easier to level. Yes, Blizzard actually wants you to blaze through all that content they worked so hard on. In writing this guide, I've taken into account two possibilities: one, that this is your first character (congratulations and thank you for choosing the Paladin, you don't know what you're missing), and two, this is an alt whom you need to get up to speed.
If this is your first character, It'd be a good time to note that Patch 3.2 allowed characters to learn Expert Riding (flying mounts) at Level 60. If you haven't learned it yet, go visit your nearest trainer and pick it up for 800 Gold (faction discounts apply). At Level 68, you can technically enter Northrend and start picking up quests. The flying won't be particularly useful to first characters, but will be extremely useful to alts whose Level 80 main characters can purchase the Tome of Cold Weather Flight, an account-bound consumable book, from Hira Snowdawn in Dalaran. Additionally, alts can benefit from heirloom armor and weapons to make everything faster. If you can afford the items, buy them, pass them on. As you can tell, Blizzard wants first timers to savor the content and for veteran players to get their butts to the endgame.
The Starter Zones
Unlike the crowded starting area of the Outlands, Blizzard designed two starter zones for Northrend. They're essentially the same in terms of number of quests and mobs, so generally the experience gain rate would be the same. It boils down to a choice of doing much of your adventuring in a snowy, dreary, uh, tundra or a lush and verdant, um, fjord (never mind what Wikipedia says, the staff of WoW.com are mandated to pronounce it as fah-geord). Personally, I went for the fjord.
Note that skipping the Borean Tundra means skipping the D.E.H.T.A. quest line entirely and missing out on some Achievements. But that's alright, those guys are self-righteous, anyway, and a true servant of the Light can't be distracted by some silly animal rights crusade! Of course, the reality is that the Borean Tundra also gives prettier shinies, such as the Axe of Frozen Death for leveling Retribution Paladins. There are also a variety of rings and necklaces, all awarded by quests in the area. The Howling Fjord has fewer cool stuff.
It used to be that zones were attractive because of the number of Undead and Demon mobs, but since Exorcism is now an equal opportunity whacking spell, it doesn't matter so much. The only bonus is the chance to use Holy Wrath more often, and in this case, those opportunities are about the same. Finishing all the quests in a zone will grant about a level and some change. The most sensible advice? Do both zones to squeeze the most bang for your leveling buck.
Level 72 to 74 or so
You will inevitably be led to Dragonblight, where it is imperative to complete as many quests as you can in order to participate in one of the most epic and lore-charged experiences in the game. Why is it imporant to complete as many quests? Because the massively awesome Wrath Gate cinematic and all the cool stuff thereafter only unlocks after completing a whole bunch of mini quest chains. If you're Horde, you'll need to do the quests in Westwind Refugee Camp, Venomspite, and Agmar's Hammer. If you're Alliance, you'll need to do the quest in Wintergrarde Keep and Wintergarde Mine. Once you've completed the pre-requisites, the faction leaders in the zone (who, incidentally, are also duking it out in the Isle of Conquest) will send you off to see dragons, treacherous undead, and flashy moves by your faction's big shots.
At the end of the day, you'll come away with some nice loot such as flashy pants -- Wrynn's Legplates of Carnage or the Warchief's Legplates of Carnage (healing Paladins will need to pick up the spell power Mail) -- and a nifty trinket. Completing the Wrath Gate sequence will also irrevocably phase you into a different version of Azeroth where some NPCs are no longer around. Think about this whole phasing deal for now, because it looks like it will be pretty exciting in the near future. Did I mention you should level up mostly in Dragonblight for this period? Yes, I believe I did. Until you complete the epic-est quest chain, all other on-level zones are secondary.