While Paladins aren't the FotM they were at the start of Wrath, they're still an extremely popular and versatile class. Lacking only a ranged DPS spec, I have found my Paladin to be my favorite character in game so far. I've even thought about rolling another Paladin - seriously. As a tank/heal dual spec, I'm never at a loss for group finding, and I'm nigh on indestructible while questing. Yes, it takes a little longer - but hey, that's why I have another monitor with "The Shield" playing.
The Basics - and what you need to know
I'm assuming that most folks who stumble onto this site are not brand new to the game, so I'm not going to cover all the quest zones, gear choices, etc. As far as race goes, if you're horde you're going to be a Blood Elf (until Cataclysm...mmm giant cow), though if your alliance you have a few more choices.
Blood Elf - Aside from being damn hot (The difference between me and Rhidach? I make this look good), you also get Arcane Torrent. Not only is this one of the few silences you'll have available, it also returns 6% of your mana back. It's not huge, but it's enough to keep the train rolling. And honestly, nobody expects a female Belf to have 48k while running the flag in WSG. We just don't look that dangerous. Of course having a pocket Disc healer and some 5k+ heavy hitting flag returners doesn't hurt - but I'm getting off topic here.
Draenai - A close runner up to the Belf for hotness, the female space goat isn't bad. As far as racials go, having the +hit never hurts, and the Gift of the Narru HoT will scale with gear. Having a mana free heal is a good thing.
Humans - 10% faster rep gains will be important in Northrend, and Every Man for Himself is your only real fear/stun breaker. Added Expertise with swords and maces helps out as well, at least until you're in full 245 ToC gear.
Dwarves - Personally, I dislike them the most. I hate the attack animation. They do have stoneform though, which is usefull for dropping bleeds and poisons. Expertise with maces is nice, but the gun specialization is kind of a waste.
No matter what race you choose, you're now on your way to becoming one of the most hated classes in WoW. Second only to DKs and maybe gnomes of any class.
How to Level Prot
Everyone and their brother seems to suggest leveling as retribution, getting your Bloodied Arcanite Reaper, strapping on your Stockade Pauldurons, and basically auto-attacking your way to 50 when you get crusader strike. The changes to SoC are helpful here, and you get Pursuit of Justice for 20% faster movement - but you're not unstoppable yet.
Going down the protection tree lets you grind your way forward like the proverbial juggernaut. Keeping Seal of Light up, and judging Wisdom, may not kill your enemies with reckless abandon, but you will have zero down time.
Divinity - an excellent talent for leveling (and unfortunately there's no room for it at 80), this talent is a cheating machine. Simple in nature, it increases healing done by you, and to you, by 5%. This means your heals, JoL, and SoL all heal for 10% more - as they are on you, and by you. While this doesn't seem like a lot (if you had 1000 HP, JoL would return 20HP on a proc, 22HP with 5/5 Divinity), it adds up quickly over time. You also need points to move into the third tier, and this is as good a place as any to put them.
Divine Strength - 5% more Str = more threat, more damage, more parry, and more Block Value. You can't go wrong.
Tier 2 is a complete waste while leveling. Skip it entirely. We're going to depend on getting hit later for Reckoning, and teh 5% dodge from Anticipation goes against that. Be sure to get this at 80 when you're dungeoning/raiding though.
Toughness - More armor = win. Take all 5.
Improved Righteous Fury - 3% less damage taken while a passive abillity is up. Yes please.
Improved Devotion Aura - Even though you'll probably be running Ret aura for the increased damage, this is 6% more healing to anyone affected by your aura. Your healers will thank you if you're grouping, and this stacks with the 10% you get from divinity in tier one.
Improved Hammer of Justice - Reduced CD on our one stun. Take it and laugh. A lot.
Blessing of Sanctuary - Get this talent as soon as you can, and keep it up forever. With the changes in 3.2, and again in 3.2.2, this will be the only blessing you will ever run on yourself. 3% reduced damage, and mana return on every block, dodge, and parry. This is on top of the 10% increase to both Stam and Str. Let the good times roll.
Reckoning - A 10% chance, after blocking or being hit, to generate additional attacks. In BC tanking this was a great way to get yourself parry gibbed. For leveling, it's amazing. If SoC wasn't so far in the ret tree, it would go nicely with this talent - but we'd be level 50 by that point. Stick with JoL or JoW, and watch the mana flow.
One Handed Weapon Specialization - You're going to be sword and boarding it anyway, increased damage can't hurt.
Sacred Duty - 8% more Stamina. The CD reduction on our bubble and "bubble wall" is just icing on the cake.
Ardent Defender - Easily the most overpowered "OH NOVOS!" talent in the game. It took a slight nerf in 3.2.2, but 20% damage reduction to anything that hits you (or pushes you) below 35%, and a permanent auto-self rez so you can keep on fighting. Your HP return is based on your defense (for your level) so you probably won't be getting the full 30% back - but it does buy you a few extra seconds. In the end game, this talent is priceless.
Holy Shield - More blocking, and more damage while blocking. Take it and keep it up.
Spiritual Attunement - It looks good on paper, but unless you're really lucky and just chain running instances, it's a waste. Come back and put one point in it later if you have to - skip it for now.
Combat Expertise - You're really taking this for the 6% stamina at this point. The Expertise is just a bonus.
Redoubt - More BV and more Block total. Great talent if you're AoE grinding - which your supposed to be doing by now.
Avenger's Shield - The real reason we all rolled Protadins at the start. We all want to be Captain America.
Guarded by the Light - Absolutely necessary at 80 when you finally get Divine Plea. Pretty meh until then. Skip it for now, save points for when your 79 and 80.
Touched by the Light - Needed for threat when tanking at 80, not needed for the grind up. Skip it until you become a grownup tankadin.
Shield of the Templar - 3% damage reduction, and gives your Avenger's shield an interrupt/silence effect. Now if we could just lower the cooldown...
Judgements of the Just - Our version of Thunder Clap, it slows down melee attack speeds. Another 20 seconds off your Hammer of Justice is another big bonus. Plus, we need these two points to get us to...
Hammer of the Righteous - This bad boy will proc your JoL or JoW on every target it hits. Glyph it IMMEDIATELY, so you'll tap an additional target with it. Running low on mana? Swap to JoW and hit this bad boy in a crowd. Top yourself off, and keep on trucking.
By now you should have 51 points in protection, and are sitting at level 60 in the Outlands. At this point move to the Retribution tree, pick up Defelction, and start working your way towards Pursuit of Justice and Vindication. Benediction will increase your longevity by reducing mana costs (everything but our heals is an instant cast), and any of these talents will serve you well.
Things to Remember
Free mount at level 20 - go get it.
Shield and a 1H - leave the 2H to leveling warriors and DKs.
Hand of Reckoning - Does a silly amount of damage to a target that doesn't have you targeted. Use it to pull before your shield (especially at low levels) and it's a good finisher until you get Hammer of Wrath (on fleeing targets only).
When fighting targets that run, judge Justice. It will save you those extra mobs you might not be ready for.
Blessing of Might until you get Sanctuary. After that, it's the only Blessing you'll need.
Don't worry about stacking 'tank' gear, any plate with Str or Stam will do. The goal isn't to be defense capped, it's to just grind your way up.
Keep RF up even when you're soloing - you have it for the damage reduction, not the threat. Now that it doesn't have a time limit on the buff, it should be easy to remember.
Seal Swapping - Remember the goal is zero down time, so switch seals/judgements as necessary. Be flexible.
Faster is better - use the fastest 1H you can find, even if it's a white weapon. If you can afford to get an heirloom weapon, you'll be double dipping as they seem to have both spellpower and AP/Crit. Get the thrash blade if you can, the more attacks the better.
Avoid AV until 3.3. The rewards have been halved, but at least you won't have to worry about running into a lvl 80 with full Season 6/7 gear or ToC - though the jump to 80 will be rough though. Ignore this if you're running both heirloom XP pieces, that should offset the diminished rewards at 70. XP is so fast in the outlands though, that you shouldn't have a problem.
If you can, tank your way through the Outlands. There's DKs a plenty, and none of them seem to know how to tank. If you're really feeling gutsy, you can heal your way to 70 with a dual spec. Once you hit Northrend though, you shouldn't have a problem finding your way into dungeons.
It's not as sexy as Ret, but with little to know downtime - and being nigh on to unkillable if you don't get carried away - leveling prot is a great grind to 80. You'll have the basics of the 9/6/9 rotation already ingrained, and as long as you start collecting tank based gear in Northrend, you should be ready for regular 80 instances by the time you get there.
Thanks to Old Man Feffy for reminding me of this grind spec.
Questions? Post em in the comments!