My advice would be to look at the finished maps and browse the thumbnails and look at the ones with the style you like the most - or ones which you think with a good effort you could take a shot at recreating and then seeing what software was used to make it. If that's coming up with the same software each time then head for that. Sometimes that might be a good old fashioned pen but there's lots of choices.
We have a tutorials section covering many of the apps. Try following some of them and when your comfortable with some then you can develop your own style or move away from a preset formula.
As always, post your work in progress (WIP) images for a map in a new thread and get some feedback and tips from the users here. The main ingredient to all mapping is that 110% or dedication - the rest is all just cranking the handle.