This guide has helped very much in showing locations of wild horses and explaining how to catch/tame them: http://violetastray.com/bdo-horse-taming-and-locations/
Basically, you need a capturing rope, get some lumps of sugar, and be prepared to do a bit of button smashing and timing in a minigame.
Lumps of sugar can be made through heating in the processing screen. Use 10 Raw Sugar and 1 Mineral Water. These can be bought from cook stores.
If you're successful, you'll take you're newly captured horse to a stable, register him/her, and get some XP.
The other option is to train your horses by riding them. You can AFK train in Xbox BDO by being in your map and setting a looping waypoint with LT+X. Horses will also eat carrots automatically from inventory when doing auto-running by clicking Left Analog stick. (They only eat when stamina is almost 0)
Suggestion from what I've seen and based on some guides I've read. Train your horse to lv15, than move on because the XP required for the horse levels past that are a lot higher than what's really worth for the XP you get towards your training skill.
I sell my T1 horses I've captured to make room for new horses to capture (or buy if you don't want to go hunting for them).
Online guides also suggest to not train with wagons because it splits the XP across the 4 horses, and wagons are slower and the horse earns XP based on distance traveled.
There are also foods, outfits, boosts, and crystals that can be bought, earned, or made to earn more XP for either the horse or the training skill.