It depends. There is a software forum and a thread with hundreds of apps listed, but you have to determine what will work best for you. I started with Fractal Mapper 8, but migrated to Gimp when I realized I "wanted" far more control over the final output. For some people, price is important, be that free only, low cost(for your definition of low cost), or "money is no object".. For others, a specific style is more important and some software is just plain better at producing a specific style than another.
Perhaps the best thing you can do is look around at the various maps here, find some you like, and then see what the artist used to make them to give you an idea. Personally, I use Gimp because it's free and runs on multiple platforms(linux specifically). There are some things it can't do(or at least not easily) though and for those things other software is better(I don't do those kinds of maps, so it's not important for me).