The stable masters in the major cities (Heidel, Calpheon, etc) will give you access to the horse market. You can buy horses that other players list for sale or you can go tame your own (watch a video before attempting to tame your own cause there's a step that most guides dont accurately describe in text). The stablemaster in Heidel (I think it's Heidel, might be Velia) gives you a quest to tame your first horse.