They first became available in Ultima I, then known as a "cart". In Ultima VII, only carriages were offered by the stables, due to that installment's engine limitations. However, they really presented little to no advantage over walking by foot, and superior transportation such as the magic carpet and moongates, become available quickly enough that carriages were often underused.
There is no faster mode of land travel that riding in a horsedrawn wagon. When travelling in the wilderness, the quicker one is, the safer one is. Horses and carts can be purchased from the stables in Britain.