For example, a Novice will be able to fast travel to a new location after visiting it 20 times.
An Apprentice will be able to fast travel after 15 times.
A Journeyman can fast travel after 10 times, and can fast-travel directly to city stables.
An Expert can do it after 5 times.
And a Master can do it after only visiting once, and can fast-travel directly into cities, automatically stabling their horse.
You can have a fast-travel location added to your map by the use of unique pickups. For example, you might find an object called "Map to Anvil" on Oblivion, and that will add Anvil as a fast-travel location.
Additionally, the game would have a silt-strider style of travel, and if you use that instead of walking, it counts towards your "Times Visited" for a location, but you don't get an increase in your Navigation skill.
"But Nazzer, what would there be to stop novices running out of the area and back in 20 times?"
Well, that's a simple programming concern. A player would have to travel through a certain number of cells before returning. Using Oblivion as my example again, they could travel between Kvatch and Anvil a few times, or just wander the area around Anvil. This simulates getting to know an area before understanding where it is.
I think my system would be a happy medium between Morrowind's manual travel focus and Oblivion's fast-travel. You are forced to manually travel everywhere a bit before you can fast-travel, so it'll make sure no one can really complain about the tedium.
For balance reasons, it may make sense to allow players to buy maps to the major cities for some set sum of gold in addition to them being found in, say, NPC houses. Maps essentially serve the same function as Spell Books in Oblivion.