Here's an article I wrote for G*M*S Magazine that helps you decide what software is best for you. Once you figure that out go to the Software Forums here and search for pertaining software, there are many choices. You need to go to the Tutorial forum and pick one and start learning. For example, if you choose GIMP, you should try RobA's Artistic Regional Map tutorial uisng GIMP as a place to start.

No offense, not that Butch Curry's cartography videos aren't good, but you're at the Cartographers' Guild - the best place online to learn about map making, why go anywhere else???