Post Level 60, The Years of Expansion

The first 60 levels are considered Vanilla WoW, or Classic WoW. This all changes as levels 61-70 take place during the Burning Crusade expansion, and 71-80 takes players into Northrend for the latest expansion Wrath of the Lich King. The zones will change, but the message stays the same, kill unto others before hey kill unto you! Each expansion brought about massive changes to the Paladin class, and a player working through the game post launch of Wrath of the Lich King is better off for it. During Vanilla WoW, Paladins were considered a healing support class only (heal and buff bots to be precise). When Burning Crusade changes took effect, the Paladin came into its own as a solid tanking class (thus the Tankadin was born). It wasn't until most recently that the Retribution tree and accompanying spells provided Paladins a way to enter as a true damage dealing class. Since the progression from 61-80 is probably a solo endeavor, please check in on the other guides for leveling from 1-40 and 41-60. Enough history, let's move on to how life is different post level 60. 

Auras, Spells, Seals and a partridge in a pear tree

Aura Dancing
Up until level 60, it's fairly common to have one Aura as a staple (i.e. Devotion Aura). That all changes when you get Crusader Aura. This handy Aura gets you and your group mates places faster, and everyone will love you for it. They won't love you if you forget to switch back to the appropriate Aura when the group rolls into battle though. Helpful tip: keep an eye on those Auras! It's easy to set them and forget them, but you will be doing yourself and party a disservice if you don't watch those.

Can you Spell drought?
Through 20 levels from 61-80 there are exactly 4 new spells added to the Paladins repertoire. That's it. Of course that doesn't include Seals, Auras, Talents, or upgrades to previous spells. The good news is that the spells are well worth the wait. Let's look briefly at them and how they will help a solo player advance to the level cap.

Avenging Wrath
Every 3 minutes, a Paladin can do 20% more damage and healing. Use this early and often with one caveat; make sure you won't need to bubble for 30 seconds because Avenging Wrath places a debuff on you preventing bubbles. It's a classic risk versus reward spell. More damage and healing, but you may wish you hadn't if you overpull too many bad guys.

Divine Plea
Another interesting risk/reward spell that replenishes mana at the expense of healing. While soloing, use this spell every time it is available, period. The debuff isn't that long and mana replenishment is excellent. Use this spell a lot, did I mention that already?

Shield of Righteousness
A shield-bearer only spell, this is a damage spell for the Paladins leveling as protection for the most part. The damage this spell dishes out is enough to make it worthy for damage and not just generating threat in a group situation.

Sacred Shield
The "Oh No! Save me or I"m gonna die!" spell. This spell puts an immediate barrier of 500 hit points around the target and provides a 50% chance for the Paladin to crit with Flash of Light. Barrier against damage is good, extra healing crits are always good. Probably not used a lot in soloing, this will become a friend during group battles.

Seals: When does 2 plus 2 equal 2?
There are four seals added between levels 60 and 70, none post 70. The four seals are really two seals with Horde and Alliance flavoring. The Horde gets Seal of Blood and Seal of Corruption which are more Horde-like names than the Alliance versions of Seal of the Martyr and Seal of Vengeance, respectively.

Seal of Blood/Martyr are more of a raiding tactic where the Paladin is likely to be receiving periodic heals from someone else to offset the damage from this seal.

Seal of Corruption/Vengeance are a Paladin's version of a damage over time (DOT) spell. The Seal stacks up to five times on a mob and causes more periodic damage per stack. The Paladin usually doesn't let things live long enough for this to be very effective on most mobs though, so try this out on longer fights to determine it's usefulness for yourself.

At level 61 you're not in Kansas anymore.
The Burning Crusade lore is all about Demons marching on Outland on their way to Azeroth. The heroes (that's you) are dispatched to in turn dispatch the demons. The leveling in Outlands is superb for Paladins (especially since the leveling curve was shortened up to level 70). As discussed previously, Paladins excel against demons and undead. Lucky for us, the zones of Hellfire Peninsula, Netherstorm and Shadowmoon Valley are loaded with demon targets. If undead are more your style, head to The Bone Wastes (in Terokkar Forest) and don't forget the large undead city of Kirin'Var Village in the Southeast of Netherstorm.

Off to the frozen tundra at level 71.
With Arthas the Lich King, ruler of undead presiding over Northrend, it is a safe bet that there are a lot of undead targets for any swinger of the light. Both starting zones (Borean Tundra and Howling Fjord (the "J" is silent people!) have undead targets ripe for the picking. And it doesn't stop there, every zone has undead enemies so keep that Exorcism spell handy!

Gear Grab Bag
Questing through Outland and Burning Crusade will keep your Paladin up to date in decent gear. While you probably won't end up in epic items, there are some very good rare (blue named) gear from quest rewards. Some may require a 5-10 minute group session, but can be worth it. The Ring of Blood in Nagrand offers up some great weapons and the group quests in Northrend (namely Zul'Drak)  typically offer very good rewards. My solo tactic is to level past the quests rated for 3 people and then come back at a level or two higher and solo the quest. Paladins are that tough and we can do what a lot of other classes can't; namely deal damage and be able to take a hit.

In closing...
Even though there are not a lot of abilities added during these last levels, a level 80 Paladin will have a screen full of action buttons. Don't get overwhelmed though, remember to keep it simple. Work on Aura and Seal rotations which are more general and then spells and Judgements that are specific to the action taking place. For casters and runners, keep your stuns (Hammer of Justice and Repentance the Retribution Talent) available. Try and start working in the spells with longer cooldowns like Avenging Wrath so you don't miss out on doing more damage (or getting more healing power). Use Seal of the Martyr/Blood to determine when you would use it. Watch the cool downs of various spells and work through the rotation of Judgements and attacks to find the most efficient way of staying out of cooldown territory.