With Adobe Photoshop CS4 and the tutorials on this site you can create pretty much anything, so I really wouldn't worry about software (most tutorials here are for Photoshop as well).

The best thing you can do is go to the Tutorials/How-To section of the forums and browse, browse, browse; read anything and everything that has a title that grabs you. There are plenty of tutorials covering a whole range of map styles (from a real-world atlas to an antique map) that will cover pretty much all the basics. There are also plenty of "mini tutorials" that will not be as all encompassing but important none the less, synthesizing all these resources together is the key to developing beautiful and unique maps.

For example, I stumbled upon this site one day and spent hours reading through tutorial after tutorial gaining inspiration and knowledge and then just took the plunge and started making a map. Don't be daunted by what you see others have accomplished, when it comes down to the bare bones of it almost everyone started their map with difference clouds and a threshold adjustment layer.

I would also recommend that you don't dive right into your HUGE project, begin with a smaller map to get your feet wet and start learning the tools of the trade. Also, open up a thread in the Regional/World Mapping section when you have a work in progress and get criticism from fellow members.

Hope all that helps! I'm eager to see what you come up with.