When you start a new character you receive a gift box with a horse whistle box (among other things). Opening that box gives you a horse whistle that is good for 24 hours from the time you open it. Once it has expired you will receive a letter from Eogar of Hengstacer Farm in Bree-Land inviting you to visit and learn how you can own one of his fine horses.
There are two ways to earn the Characteristic: Riding, and the right to buy a horse.
Once you have unlocked the Basic Riding trait you can purchase a horse from any Horse-Master.