Leveling a Paladin has never been easier than it is right now. Class mechanics of a the Paladin allow for reduced damage, total damage absorption, and total damage recovery. These are key when dealing with ANY pve and pvp situation. When questing you are going to get hit so the more armor and health you have the better off you are. I can go toe to toe with 4 mobs 3 levels higher than me and be perfectly OK. On my priest I would have been running for my life. So now you can take a hit. Can you put out the damage? Yes.
Retribution tree is all about putting out the damage. The Paladin class is all bout crits. Crit healing, crit absorption, and putting out crit damage. The ret tree has been reworked over so just about any combo of talent points you put in are going to be useful.
Glyph of seal of command is an awesome leveling glyph giving back 8% of mana when judging with it. Glpyh of judgment is nice too but look for it under 30 gold. These help so much.
Quest greens are OK when leveling but the fastest way to upgrade is the AH. When scanning the AH for upgrades search for "of the bear". Those items have a good amount of strength and stamina. Two key stats when leveling.
Open up with Hand of Reckoning > Judgement of Light > Exorcism > finish with White Damage. The mob will be dead and you will be almost at full mana.