One thing can't be said of Medieval maps, realism. They look kind of like a flat pop-up book. Objects stand out in profile, in a larger scale than the surrounding terrain. Medieval maps, like the art of the period were about conveying the importance of an object rather than its precise location. But they had style. Dragons and sea monsters roaming the edges and lots of other little touches.
When designing a game world one of the first steps is mapping it. There are a few choices; freehand, square grid and of course hex grid. True to my seat-of-the-pants-don't-sweat-the-small-stuff style of play I decided to ditch the traditional approach to mapping. If the game is set in a world without accurate maps then why should the players' be. Tony Dowler's blog year of the dungeon has some great maps already done. Here is a sample;
Compare that to a medieval town map;
Similar yes? And finally another from Tony's blog showing the city of Salutet and its surrounding area.
Simple easy maps that have all the info you need. A very minimalist approach. Very old school. And because they are not a lot of details on the map, there can be a lot more in your imagination. Very old school indeed.
P.S. Check out year of the dungeon for Tony's one page dungeons.