I want to see a "Navigation" skill added to the game. With a low skill, NPC directions don't give you a very good map marker. Using Balmora from Morrowind as an example, once you get the directions you'll know the general location of the place represented by a circle within a range around the location, but not centered on the location. Once you travel there, your map marker will be a bit better, perhaps with the circle getting smaller as you become more familiar with the location. Eventually, after manually traveling there many times, you will know exactly where it is, and can finally fast-travel there. When you fast-travel at a lower skill, though, you aren't always going to be close to your destination. For example, you might have only visited Cheydinall twice with a low Nav skill, so you arrive about a thousand yards away from your destination. Traveling around and reading maps you can pick up in the environment will increase your navigation skill, and you will be able to learn locations faster. Traveling away from roads will improve your skill faster.
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.
I think it should be done with landmarks and routes instead of times visited, and it needs to be in conjunction with the survival skill.
Maps like http://media.giantbomb.com/uploads/0/6812/208206-black_marsh_map_oblivion_large.jpg look good in the game, and they aren't terribly time consuming to put out. Considering that, I say they make a ton of the maps and integrate them into the game world.
I'd firstly suggest that you'd have to buy all the maps you were going to use, as well as the compass. They had a wet compass in Redguard, so we know they can be items. Next, you'd need to buy the map or get the guide to the town if you wanted anything zoomed in. Buildings wouldn't have mini-maps or anything, they weren't tourist friendly. For more detailed maps of places outside the city, you'd have to talk up scouts and local mapmakers to get a map of the smaller piece of terrain, and to put landmarks and locations on there. As always, you can either pay for information about the area, or you can work for it with exploration.
Using the maps this way, you can also use them to fast travel. The map interface should be in this http://multiplayerblog.mtv.com/wp-content/uploads/2008/09/fcry2mapbig.jpg so you don't have to be in a menu to operate. The animation to bring those out looked alright too.
To fast travel with them, you'll need to be able to navagate the paths, edges, districts, nodes and landmarks. The more you know, the better you'll be able to fast travel. The Outdoorsman skill will let you be better at dead reckoning and fast travel off the roads, while better Equestrianism skill will let you evade fast travel traps along the way.
When you get a quest from someone, they'll point to where it is on your most relevant map and you'll mark it. None of that quest marker business, so you can't mark people with it. Only locations.
As a standard, many maps need to be wrong, or just flat out lies. In this time, the boundaries are only somewhat agreed upon. Disputes over borders are still a common thing, and maps are one of the best ways to lay claim to something. Each noble would likely have his own type of map for his or her interests, and make their subjects see it their way. There shouldn't really be an official map of what is what in the world, and the overall map needs to look quite a bit like the basic Oblivion map. It shows the major cities, a couple major roads, and the basic outlines of topography, but it's pretty sparse.
Then, maps by membership. Chances are that they aren't going to map every wayshrine of Arkay on a merchant's travel map, so you'd have to talk to the right people. Find someone in the town who worships Arkay, and don't forget that the society is henotheistic. Believing in Mara doesn't mean you give a crap about Kynareth. Getting maps as rewards again will be a great thing.
Lastly, you can sell locations to people. If you find an unmarked trade route, you can sell that info to some bandits. If you find out where the Baron's summer getaway house is, you can tell his enemies, or for a lesser price the Thieves guild. The guild might resell the info to the Baron's enemies, and clean house once they're through with the place. You guys might remember in Daggerfall being able to choose how you finish quests by taking evidence to someone related to the quest for a different outcome. There was a time Helseth was having you deliver a message for him, but you could take it to Barenziah for her approval and reward. You'll also remember revealing the mine to the elf in Vivic city in Morrowind, and that he gave you a daedric weapon for it. That's the kind of deals you should be able to work out. It's up to you to find and sell what they might be interested in.