Think about what the purpose of such a map is. Medieval maps tend to fall into three categories:
- road maps (for travelers by road)
- coastal maps for (travelers by sea)
- maps of the world (for general information)
Road Maps
If it's for pilgrims and merchants traveling by road, it'll have all the major roads marked, along with inns and convenient places to stop to water the animals -- and it won't describe the wilderness or the sea at all. Take a look at the Tabula Peutingeriana for an example of a classical/medieval road map.

This shows how far it is from one town to the next, a few other things you might find along the way, and some general indications of where the mountains and rivers are to help keep you oriented.
Unfortunately, it's out of date. Really out of date. This copy was made in the 1200s, yet it shows cities and roads that hadn't been around since the fall of the Roman Empire. It even shows Pompeii as a city, which had been destroyed at least eleven centuries earlier.
Coastal Maps
If it's for seafarers, it'll have all the harbors and rocky shoals marked, along with notes about winds and whirlpools in the sea. It won't say anything about what you'd find further inland. Take a look at some medieval seafarer's maps, called Portolan charts.

These actually do a pretty good job of showing what you need to know. The coastline is densely filled with ports here, divided into major and minor ones by the color of the text.
World Maps
If it's a map of the whole world, it'll try to include all the regions that the mapmaker has ever heard of. The areas near home will be fairly good, but the further away you get, the more vague and fantastical you get. Take a look at any of the Mappa Mundi and see how Europe and the Mediterranean tend to have all the right parts, while India and China get pretty speculative.

Many medieval world maps were more theological/philosophical than geographical. A typical Mappa Mundi puts the world in a round shape that's easy to comprehend, with Jerusalem at or a bit above the center, and the Garden of Eden towards the top (which is east, not north).
Some medieval world maps were much more accurate. Ptolemy, in the 2nd century, compiled a list of coordinates of locations for places throughout the known world, giving longitude and latitude for each. With these coordinates (and a projection of a sphere onto a flat sheet of paper), people during the Middle Ages could (and did) draw up a pretty decent world map.

Modern Maps
Modern maps often aim for somewhere in the middle. All the maps above are of the same region (except for Ptolemy's map). Now take a look at how Google Maps renders it:

This map doesn't tell you how long it takes to get from one town to another, it doesn't tell you anything about the bays and harbors, and it doesn't even show rivers at all. If you're looking for those features, one of the medieval maps would be better.
The modern map is like Ptolemy's map: it's all about getting the features in the right place compared to each other. The medieval road map might tell you exactly how long it takes to get somewhere, but the modern map tells you exactly where it is.
A traveler doesn't need to see every little kink in the road or every administrative boundary. They need to see how to get where they're going.