I agree with ascension - make a not so detailed world map or region map, and then throw in some smaller maps of where things happen, regions, citys etc. In most novels you only get one map, but I love when there are more.
The publisher will be pleased to recieve any map, vector or raster - as long as it is good enough to print. So what ever program you are confortable with will work. Just remember if you choose raster that for real printing you have to have 300 dpi resolution, so a 4x6 inches page would be 1200 x 1800 pixels
It is always possible to scale down (and texts in photoshop remain vector until you print) but its not possible to scale up very far (20-30% and then the quality might start to suffer).