fog of war is good, and maps as well, just think of the map as you would draw them as you explore the area, what would be better is that your character says: "hmm, behind the busshes seems to be a cave entrance to me" and that it gets pointed out on the map.
that way you know that there is something there.
great idea viper <img src="/ubbthreads/images/graemlins/biggrin.gif" alt="" />
and handefood has good idea too! <img src="/ubbthreads/images/graemlins/biggrin.gif" alt="" />
I like that. You could purchase a map which has the roads and towns and shops etc. on it in ink, and as you scout the area, the map fills in with life-like colour. That way, you're not left blind as to which route to take or where unmissable landmarks are, but the things that commoners don't know about are still hidden until you find them. By colouring in the map as you explore, it would also appease those who use the fog-of-war as a guide to where they haven't been yet.