Templar, Defenders of the Faith, requires weapon focus in your deity's favored weapon, endurance, and umm... something else I think, plus 8 ranks in knowledge religion. Damn good class, gets fort and will, fighter BAB, more smites, bonus feats, damage reduction, and a good fightery spell list, and best of all, you can take it at level 6.
Hospitaler, also Defenders of the Faith, requires Mounted Combat, Ride By Attack, and some other riding feat I think. Don't remember what the level restriction is, but it's something around 7 or 8 I believe. Ignore most of what it says in the book, it has been errataed fairly heavily. Adds hospitaler level -2 to your turn undead effective cleric level. Adds to lay on hands, gets two domains and +1 caster level per level. Fighter BAB, bonus feats... all to the good.
Those are the only two WoTC prestige classes that work for paladins. There are other ones paladins can take, but their abilities aren't aimed towards paladins.
-The Souljourner