I have a paladin character. How can I ride a horse?
When a character reaches level 20, they'll be able to get the Apprentice Riding skill from any Riding trainer (ask a guard where to find one in a capital city, like Stormwind). Then, you can purchase any mount and use it by going to your mount character pane and selecting it.
However, since you're a Paladin, check with your class trainer at level 20 to get the Summon Warhorse ability (if you're not Draenei or Tauren), the Summon Exarch's Elekk ability (if you are a Draenei), or the Summon Sunwalker Kodo ability (if you are a Tauren). This will grant you the Apprentice Riding skill mentioned above and a special, class-only mount. You can then purchase regular mounts if you so desire.