The Paladin class is pretty flexible and has a variety of choices when it comes to specs. You can go with Holy, if you want to be the party healer; Protection is great for tanking (or AOE grinding, if that's your thing); and then, Retribution, which is for kickass DPS.

Now assuming you want to level fast, which you do, then the best paladin leveling build for fast leveling is definitely going to be Retribution. Going all out on the DPS will get you to level 80 the fastest.

You don't want to completely spec Retribution though as it is worth saving some talent points to drop them into Holy and Protection. Since you are going into battle often, you want to improve your durability and recovery time a bit. It'll keep you from dying which can really slow down your leveling speed ;) Actually, what it will really do for you is help decrease your downtime, i.e. time spent healing etc so then you can just keep on going.

Now everyone has their own favorite wow paladin build that they think is going to be the fastest, so some might disagree. But this works pretty well, I think. Try out these specs and see what happens.

Here's my picks for "must haves" with the number of points for each one, keeping in mind that this is for fast leveling. Notice that you've got some Holy and Protection in there as well as 15 points in Retribution.

• Spiritual Focus (Holy) - 5 points
• Improved Devotion Aura (Protection) - 5 points
• Improved Blessing of Might (Retribution) 5 points
• Improved Seal of Crusader (Retribution) - 5 points
• Seal of Command (Retribution) - 1 point

After these, there's some other great options on the Retribution tree you should consider:

• Benediction
• Improved Judgment
• Conviction
• Pursuit of Justice
• Two-Handed Weapon Specialization

Benediction will help improve some of your crappy mana efficiency. Pursuit of Justice will aid your desire to level fast. You'll save a lot of time between quests, so I would spec this as soon as you can. The rest are highly helpful for DPS and beating the crap out of things is going to be your fastest leveling option.

Now as you go through the levels to 80, you should just respec your Paladin when you feel it is necessary. The Paladin talent calculator on Wowhead can be a big help sorting out where to put points, so be sure to use it.