Paladins are the most limited class in the game in terms of ranged damage. They cannot use any ranged weapons. [Exorcism] is the only ranged damage opportunity before [Holy Shock] (for the Holy Paladin), although it only effects daemons and the undead; meanwhile the limited-use [Hammer of Wrath] becomes available at mid-levels. Due to this ranged limitation, [Engineering] is a good choice for Paladins because of its various ranged explosive and guardian-type devices.
The Paladin's ability to wear mail/plate, use shields, and wield almost all types of melee weapons makes [Blacksmithing] a good choice if [Mining] is chosen as a gathering profession. Paladins will be able to produce highly sought-after shield and weapon enhancements such as weight/sharpening stones, shield spikes, and weapon chains that counter disarm effects.
[Alchemy] offers a wide variety of potions, elixirs, and the much sought after flasks that boost health and mana, and provide additional temporary traits and bonuses to existing stats. It is a profession useful to any class, and a typical 40-man raid will find themselves in need of at least one Alchemist.
[First Aid] is recommended as a fair backup healing plan for when mana is exhausted, if you intend your Paladin to be a healer-type. It also is useful to any class. Take note that high-level first aid is necessary for the Loatheb encounter in Naxxramas.
[Cooking] allows you to learn recipes that give you short-term Stamina or other bonuses, which is always useful to any class.
Other classes do little to benefit paladins directly, and their roles could be commisioned out to other classes by the Paladin.