J.R.R. Tolkien once said, in reference to his vast works regarding the world of middle-earth, "I wisely started with a map." David Eddings, author of the Belgariad and Malloreon as well as the Elenium and Tamuli fantasy series adamantly states that it is vital to have a map when you start out writing fantasy (or building it in NWN). If you don't you are going to get lost and make the story inconsistent.
AutoREALM is an open source map design package created for RPG gaming. It is available for free and is as powerful a tool as anything you could ask for. It does fractal coastlines and rivers, has icon sets for trees, cities, castles, etc., and can generate maps on square, triangle, diamond or hex graph paper (if desired). It is available here.