I have an earlier answer about medieval travel infrastructure that discusses how travellers figured out where to go and stay, and some of the laws that attempted to protect them. (It's also got a lot more; hope that's okay for now.)
I'll also add up here two of my favorite medieval travel trivia:
Western medieval Europe had plenty of roads beyond the viae Romanae...but sometimes we are talking "roads." They could be as developed as a path trampled down the middle of a field. By the late Middle Ages, some places had laws that if said trampled down path was a lake of mud...you could trample a new path right along next to it.
From accounts of pilgrimages to Rome during major festivals, apparently people used to camp outside the city in tents.
Anyway, onward!
~~
Could the experience of travel really get all that much better in the late Middle Ages? After all: a horse is still a horse, a camel is still a camel, most people still walk, and the Mediterranean is still trying to kill you.
It turns out that the most important improvements involve the human infrastructure of travel. This sounds recursive and obvious when taken broadly--more people traveled because traveling was easier because more people traveled. So let's talk some specifics.
Medieval people traveled, but they typically did so with a purpose: a destination in mind. But as Ruth Evans notes, one of the biggest puzzles of late medieval travel narratives is how completely unconcerned people seem to be with figuring out directions. There absolutely are "guidebooks" of sorts from the later period, especially with the popularization of cheaper paper over vellum. Many of these seem to have been of minimal practical use, since a lot of the places noted are more symbolic than practical; plus there are the problems of literacy (really the big one here) and hauling along an expensive codex with all your other baggage. Then there are the problems of medieval street addresses. Streets and city quarters might be designated by a name or description, but you weren't handed a neat little map upon paying an entry toll. And houses/buildings weren't designated by numbers to be counted, but rather given names according to little signs/statues on the exterior--the House of the Three Kings, the House of the Weeping Virgin Mary, and so forth.
The most obvious answer is also the one hinted at in textual sources: human guides! This could mean an actual guide for the journey, or simply talking to local people asking where to go next. And this is where "more people traveling" came in handy. Villagers who have been traveling to multiple market towns thanks to increasing specialization will know the immediate countryside better than those who made a monthly journey to one. A monastery liaison who finds himself pointing hosting more and more travelers is going to become familiar with where they're going to and coming from. A set route traversed by more and more people might even acquire known guides who accompany travelers for a fee. This might be particularly helpful for travelers who wanted to minimize the number of people they interacted with along the way (that is, who might recognize them, or recount the meeting to someone else who asked).
This proto-"travel industry" was particularly useful and structured for some of the longest and most famous trips of the Middle Ages: long-distance pilgrimage, especially to Jerusalem. Nicole Chareyron has done really fascinating work reconstructing the travel infrastructure for organized pilgrimages to Jerusalem (like the one famously undertaken by 15C English holy woman and author Margery Kempe), down to notes about how the bribe system between Christian ship captains, Italian-Arabic translators, and Muslim "customs agents" worked.
In addition to "travel professionals" who got paid to help other people travel, many of whom would nevertheless have been themselves stationary, improvements in medieval travel also benefited from the increase in professional travelers, that is, messengers and diplomats. Experience over the same route is an obvious factor, especially for royal-papal couriers. The later Middle Ages saw a reduction in peripatetic (moving) courts, meaning it was much more possible to travel the same route over and over and over for years. Even in the less centralized Holy Roman Empire, the numbers of cities that hosted the Reichstag (parliament) gradually decreased over the 15th-16th centuries until it was, for all practical purposes, a Regensburg institution. The first post-Roman organized postal service in the west comes out of the HRE around 1500, reflecting the normalization of standard routes and the professionalization of a messenger corps.
The increase in salaried cursores and nuncii also contributed to better travel in a less obvious way. Traditionally, international and papal diplomats were drawn from the higher nobility (it was an honor to convey the king's message!). And, well, nobles had certain demands of comfort for their travels. Plöger and Boyer both highlight how slow a giant diplomatic familia had to move thanks to all the Stuff noble diplomats required. A single messenger could make 4-7 times as much progress in a day.
The rise in professionalized diplomatic corps relates to the growing power of more centralized government (though we are still deep down into the age of the power of regional princes,n.b.), which aided travel in a very important way: laws protecting travelers and, to some extent, the ability to enforce them. Some of the earliest privileges had to be extended to traveling scholars, who in the 12th century were getting kidnapped and held for ransom at an apparently alarming rate. (One of the "privileges" associated with a university degree even today goes back to those travel protections). Late medieval diplomats had a sort of agreed-upon diplomatic immunity, but could even secure extra protections from the territories they had to traverse. It seems likely that there were also special markers for pilgrims that would hopefully have afforded them some protection, at least from marauding lords if not necessarily bandits.
By way of physical infrastructure, there are a couple of definite developments, although their overall importance in making travel easier is surprisingly questionable. First, the age of more travelers was also the age that nobles and royals paid more attention to profit maximization of their lands (coinciding, of course, with the rise in paid/professional soldiers and importance of conspicuous consumption as a show of power). This meant more toll stations to extract more money from more travelers. Boyer discusses how, in France at least, the rise in tolls and toll-castles shifted preferred travel routes over the centuries, as people sought to pay the least they could. On the other hand, extra money paid in tolls also helped fund physical infrastructure, especially the upkeep of bridges. (Can't build a stone castle on a creaky wood bridge; can't have the stone bridge collapsing if it's going to destroy the toll castle as well!)
Second, there were some significant improvements in shipbuilding geared towards the problems of boating the Mediterranean specifically. According to Pryor, around the mid-14th century earlier efforts at combining ship improvements from both Latin and Islamic worlds resulted in enough advantage to result in their widespread (trans-religionist) adoption. Hull shape and the use of multiple sails were a couple of big ones. These allowed sailors, in theory, to better fight the winds on the east-to-west journey that had previously been all but impossible in the winter. The use of sail-ships over rowed galleys, too, allowed for more use of open sea rather than always hugging the coastline. This was especially valuable for the southern route, considered much more treacherous travel than the north.
But Pryor continues on that these developments, while obviously profitable enough to result in their popularization, had less of an effect that we might expect. Sailors still largely preferred the northern route, and on merchant-based runs, stuck to the coastline for more access to trade opportunities. The biggest displayed improvement would probably be the easier winter travel.
So overall, improvements in human infrastructure were critical in better, faster travel experiences in the late Middle Ages. However, changes to the physical infrastructure--often spurred by the increase in travel in the first place--played a significant role in shaping what travel might look like.