Welcome to the Guild Emmerich! You are in good company, many of here are on the same quest. Have a look through the work posted the finished maps section to get a sense of the breadth of different styles there are, it might inspire you or give you some references to work from. You also should spend some time getting to know the Tutorials section. There are tons of great walk throughs for various mapping software in various styles. If you have Photoshop CS, then you already have a very powerful graphics software to work with. If not, download GIMP, it's not quite as powerful of versatile but for a freeware program it is amazing, and it is also well supported here (It's what I use and I've written a few tutorials for it myself). Best of luck on your project.

Cheers,
-Arsheesh