Hmm....software, as in computers, I'm not sure. Unless you want to digitally draw a map then I recomend either adobe photoshop or sketchbook.
Something I've found helpful for making a map is one or both of these two tricks.
1. Map out your hero's journey. Where does it start, where does he go, where does the journey end? After you have that sketched out then start sketching around it. You can do this for side characters and the antagonist to build your map too.
2. Look at your world in your mind. Did it pop up on its own? Is it leeching from a place you've been? Is it similar to a place you know? If so get a map of that place, place it under a paper or scan it into a computer and tweak it until you have a new map.
I personally start my drawing it in a very rough form. Afterwards, I try to draw/shape the world I just drew into Photoshop. Using tons of layers, including plate tectonics(makes it easier to make realistic mountains) I get the result I want. From ocean to lakes and land. Once that is done, I get to the drawing board again and start drawing my handmade brushes (castles/towers/cities/trees/mountains/hills/...) Once I'm pleased with them, I import them and start putting them on the right locations.
And in the end you could end up with a stunning result.
Take note that I don't use colors, I work grey-scale. I've never had a book in my hands with a colored map. So this way I don't need to color-fill my brushes.
Second, I create my maps in a very high resolution and shrink it afterwards. This allows me to cover up some roughness's
If you mean a software whereby you just plug in some numbers and it generates a map for you or anything, then sorry, don't know any software that can help you with that.
If its just a graphics program then I recommend Photoshop or GIMP. GIMP is free but I personally hate it. I hear some favourable things about Autodesk Sketchbook, its designed only to paint and do that (hence simple). I haven't personally tried the program myself however. I craft all my maps in Photoshop and that certainly isn't the most fastest way, but you get the best results when you know what you're doing and put the effort into it.
As Varamyrr has said, work on a bigger resolution/canvas. You have more elbow room if you work in a bigger document. Keep in mind that however a bigger canvas will require more memory. Shrink it afterwards if necessary, to hide small mistakes or if file size is a constraint when uploading.
What I sometimes do is just copy geographical maps of real places (incl. rivers, cities, forests, etc.), and rotate them around and rearranging them. I might just take a geographical map of Malaysia, rotate it 90 degrees and then place it next to a rotated geographical map of Lithuania, which I had enlarged. Of course, you can edit locations of cities and rivers, etc depending on how your story needs it.
I find that this gives you those minute details that make the maps look impressive. For this, MS Paint would be enough.
To quote 'Jurasic Park' I'm 'a real live dead dinosaur'.
Most of my early stuff was on graph paper.
Later on, I made 'text maps' using pica (?) think thats what it was - each character took up the same exact amount of space. I used that to map globes, showing how mush chorter the circumference of a given world was at say latitude +60 than at +25. Interesting exercise.
Played around a bit lately with MS Paint, which has some potential (most of the maps in books these days are black and white, MS Paint at least lets you do color.
I went with colored pens, white paper, crayon, and a scanner, and I'm more than happy with it, even when compared to most of the computer-generated maps people have posted. Pen-and-paper is the most flexible and gives me the most control over what I want the world to look like.
If you're just brainstorming, I don't think you should waste time on software. If you're going for publication, hire an artist.
I made my very first map not too long ago from pen and paper. I had an idea of what kind of land I wanted it to be (one I was familiar with) and sketched my world map from a real world map of this area. Over the course of a few sit down sessions, I tweaked and colored it with some colored pencils and the end result was better than I ever thought I could produce. I was able to hand place in details which works better for me. I have tried using photoshop but I am still learning...although its something I eventually want to get the hang of. Good luck!
ProFantasy stuff is expensive. I recommend using Autorealm and then drawing your cities and towns in.
The best alternative is to commission an artist to draw your map, possibly based on the Autorealm map. In fact, there are probably some people on here who would be willing to do it for free. If not, most casual artists would only charge about $5 per drawing.
Worry about the truly high quality maps when you're getting published, not when you're still writing.
+1 to worry about HQ maps when publishing, not writing, unless you've got means to already do HQ maps.
But anyway, draw a map, having any kind of map will help your world building. I liked drawing a world map instead of focusing in small regions, it helped me with the immersion, you stumble upon "happy accidents" there. If you know how deal with graphic softwares a good trick to get continents is to make a big undefined blob and cut it out with the lasso tool. Move and rotate the pieces around. Think in our world, in Pangaea.
Now, about HQ maps... I don't think you're going to get a HQ map for $5, maybe my standards are too high.