What is "map-travel", do you ask?
Why, it is an overview mode for traveling long distances.
How does it work?
Well, you pull up your world map and plot a course, which calculates the resources you will need and how long the journey will likely take. You then gather the needed supplies and start the journey.
You see some representation of your character on the map, traveling along your route in sped up time (maybe just a little dotted line), while interface representations show you the passage of time and the weather and your supplies and fatigue etc. (Oregon trail/ Sid Meier's Pirates).
-- At the same time, perhaps you get a "travel montage" (Indiana Jones, Lord of the Rings).
Sometimes (and by sometimes I mean very very rarely), you will run into pseudo-random encounter on the journey, and given the choice to pop out of map travel and engage the situation (Pokemon, old RPG's, Neverwinter Nights 2: Storm of Zehir ), such as an ambush by bandits or a rival faction or an assassin, or attack by a pack of wolves, or an encounter with traveling merchants, or stumbling upon some people who need help (healing or transportation/etc.).
Having high mysticism or marksmen allows your character to anticipate these situations before they happen, allowing you to go around them.
Sneak and illusion would allow you to better avoid them as well by hiding.
Speech or mercantile would help you diffuse situations,
High athletics means you can travel quicker on all terrain (though you travel faster on roads by default, and the better the road the faster you travel).
A high acrobatics allows you to travel across worse terrain more quickly, or through terrain that would be impassable to those with low acrobatics.
A high strength allows you to carry more on journeys while becoming less fatigued (you don't have to stop and rest as much).
A high endurance means you travel much farther before having to rest.
A high luck means you meet more positive encounters and less negative encounters.
A high personality means you attract travel partners who might help you if you run into trouble.
A high speed means you move faster.
A high willpower means you can travel farther before having to rest but you suffer some penalty (because you are using willpower to overcome physical tiredness).
A high alchemy allows you to travel with less supplies and "pick up" supplies/ingredients on the way.
You can travel in different modes which affects your speed, fatigue, and resource consumption.
If you are good at sneaking or illusion, you could travel in a sneak mode that covers your tracks and makes you more likely to be able to avoid unpleasant encounters, but you would travel slower and so need more resources.
If you have a high endurance or willpower, you could travel in rush mode, that makes you move faster and farther without stopping but at a detriment to your stats until you rest in an inn for a good period of time.
This is just off the top of my head if you have any suggestions for the mechanic, please post them.