I'd imagine that they traveled mostly by boat as well. The Mediterranean world was very much water based and large cities were based near water. It's a bit of a mind-twister for us moderns. We see water as an impediment, but for those about the Mediterranean sea the water was the thing that allowed them to meet and greet. Before the days of expensive roads the flat-ish sea with ample wind was much simpler to get around on. One thing to remember is that the Mediterranean is relatively calm and the currents are also relatively gentle when compared to the oceans.
Compare this to the many Persian empires, the Inca, or the Chinese dynasties and we can see just how central water was to communication and trade, and we can see just how much money was spent on roads where there was no waterway.
One point about land travel in the Roman era was how difficult it was. Caesar's Comments on the Gallic Wars is a good example of how little information travel there was between the proconsul and Rome herself. So much so, that Caesar basically had to write it all down to explain what the heck he had been doing for a few years up in Gaul with all those legions.
Many ran. The modern-day Marathon event commemorates one such message delivery.
The King's Highway of Asia Minor spanned ~1,000 km and featured expedited horseback messengers reminiscent of the US Pony Express (1860--61), and represented a roughly 1,500 year plateau in physical message delivery rates. The prime period of the King's Highway somewhat post-dates peak Rome, though earlier trade routes offered at least roughly similar capabilities.
Ships were required for overseas communications (e.g., across the Mediterranian), and excelled at bulk cargo. Horseback (or even a swift runner) was still faster for messages, in general.
There were some remote signalling methods, though these were typically capable only of transmitting a set of pre-arranged messages. Typically with flags or fire, with ranges limited to a few km, and relays required for greater distances.
(One such visual relay system did run along the King's Highway IIRC.)
Most travel was still by waterway.
And the normal people didn't travel very far at all.