Horses can be obtained only in Europe, but once brought over, they may be bred. If you have two or more horses in a colony and extra food stored in your warehouse, your colony will produce more horses. If you construct a Stable, your horses will breed twice as fast.
Horses are useful for aiding travel in the New World. Scouts and Dragoons move significantly faster than do colonists on foot. Any colonist may be mounted to create scouts and any soldier can be mounted to create dragoons.