When it comes to speccing your Paladin in World of Warcraft, you basically have three different build options to consider. They are Holy, which is primarily a healing build; Protection, which makes a great tanking or AOE grinding build; or Retribution, the DPS build, and also the best build for leveling quickly at the lower levels. Since you're interested in leveling your Paladin fast, I'm going to focus strictly on the Retribution build and specs to get you going.
Once you begin building your talent tree for your Paladin at level 10, you are primarily going to be using your points on Retribution talents, but you don't want to spec entirely in that tree. There's some Holy and Protection talents that will increase your durability and therefore make leveling a faster process because you'll have less downtime.
I'd consider the following specs mandatory:
* 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
For fast solo leveling there's a couple of different ways you can go. You can use Improved Seal of the Crusader with just 1-handed weapons for a good solo leveling speed or do Seal of Command with the two-handed weapon specialization (spend 5 points here). Improved Devotion Aura should help with the solo leveling here as well. Also, the Improved Seal of the Crusader helps increase damage with Seal of Command.
Here's some more good options for you on the Retribution tree:
* Benediction
* Improved Judgement
* Conviction
* Pursuit of Justice
* Two-Handed Weapon Specialization
Paladins tend to be rather mana inefficient so anything that reduces mana cost is going to help and that's where Benediction comes in. Improved Judgement gives you a durability edge in fighting and both Conviction and the 2-handed weapons spec will increase your DPS potential. One of my favorites here though is Pursuit of Justice. If you want to level fast, you are definitely going to want to spec for this. The speed increase as you run from one quest to the next will be significant.
Now as you level don't be afraid to re-spec your Paladin as it suits you. Many WoW players re-spec somewhere between levels 35-40 from Retribution to Protection or you can give your Paladin more hybrid characteristics by picking up some additional Holy or Protection talent. And other players may be just as happy taking the Retribution Paladin all the way to level 70.