Autorealm is pretty easy to use, but in my opinion, it doesn't produce very nice-looking results. It's said that the artist is more important than the tool, and that's true, but a good artist will almost always choose the best tools available (unless using a difficult tool is the point of the exercise).

Gimp is the king of free graphics apps, and the tutorials found here can get you mapping in a fraction of the time of trying to figure it out on your own. In addition to the two that Gally recommended, also look into RobA's venerable artistic regional map tutorial.