On Foot
Budget for 2 miles per hour, with an extra hour per 1000 foot elevation climb. This is assuming you can walk on the slope. If you are only carrying yourself (and maybe a water bottle), figure on 3 mph.
Figure you have about 8-10 hours of walking a day, will give you 15-20 miles depending on conditions (mud, hills, extreme heat/cold will slow you down).
Horse
I've heard that horses are able to do somewhere between 25 and 40 miles depending on conditions, whether or not the horse needs to forage, and how hard you push the horse. Call it 30 miles for the long haul.
Wagons/Carts
Are going to cut the horse speed in half. Or you could add more horses to make each horse's weight load much less.
Over land
If you don't have a path/road to travel on, you will probably see your speed drop significantly.
Ships
How fast is the wind blowing? I've heard that most ships can do the wind speed on a good day (holds empty, all the sails up, sympathetic wind direction to desired travel direction). But somewhere around 75% of wind velocity is more likely to occur.
Others
Steamerships I recall being given a rate of around 10 mph while going downstream and much lower when fighting the current, dirigibles I don't know, and camels (caravans) travel about the same speed as horses. Trains seem to vary. The early models were speedy at 5 mph. Now, you have bullet trains that can do 200-250 mph.
Hope this helps!