For those who can afford it, a 9th level sellspell would charge 450gp to teleport 3 passengers up to 900 miles in the blink of an eye. In a small city (population > 5000) there is an 86% chance of at least one 9th or 10th level wizard, or 10th level sorcerer (3.5ed DMG, p139). Of course, there's also the chance of a teleportation mishap, but every mode of transport has its downsides.
For everyone else, wagon trains and riverboats are still the norm. A long-haul stagecoach can cover from 70 up to 120 miles per day over well-maintained roads.
Charles O. Paullin (1932) Atlas of the Historical Geography of the United States, the University of Michigan.
Michael Graham Richard (2012) How fast could you travel across the U.S. in the 1800s?