I was poking around on EN World and found this beginning cartography tutorial by Jürgen Hubert. It uses Inkscape and GIMP, both of which are free open-source programs. Since Inkscape is a vector-based program, the maps produced can be altered without completely redoing them.
The tutorial itself looks decent, but the thread as a whole is full of links to other tools, resources, and tutorials for people interested in learning about map-making. Good stuff.