At level 20 a paladin can learn [Summon Warhorse]/[Summon Thalassian Warhorse] from a paladin trainer for 1 (90 if friendly). A warhorse is a type of horse and an Apprentice-level mount which increases movement speed by 60%. The Alliance warhorse is white and has a blue and silver livery, the blood elf mount is black and has a red and brass livery. The epic mount for paladins is called a Charger.
Patch 2.4.3 changed the level at which a paladin is eligible to learn a warhorse spell from 40 to 30 and patch 3.2.0 changed the level from 30 to level 20.
Previously, Dwarf and Human Paladins obtained the spell through a quest called The Tome of Nobility. This quest consisted of speaking with Duthorian Rall in Stormwind's Cathedral Square. In Burning Crusade, blood elf paladins obtained their warhorse from Knight-Lord Bloodvalor in Silvermoon's Farstriders' Square. This was changed shortly after the release of Burning Crusade when the spell was added as a learnable spell from the paladin trainer. This was presumably to stop the complaints of paladins getting a free mount.
Since the mount system revamp in patch 1.12.1, the paladin will obtain Apprenticeriding skill upon getting the Summon Warhorse spell from the trainer. Since patch 3.2.0, the spell no longer needs mana to summon the warhorse.