Welcome, Rascal. If you've got a head full of worldbuilding just waiting to be depicted, you're halfway there already. If you see styles you like, why don't you tackle a tutorial or three, posting work in progress as you go? You'll get plentiful suggestions and advice, and (selfishly) I plan to learn from you as well. You see, there's pretty much no mapper the rest of us can't learn SoMeThInG from, maybe even especially newbies -- you'll have your own unique ideas of how to do things I'm sure.

Do you already have some graphical tools at hand, or will this be an excuse to get some? The best projects always call for new tools, whether from the hardware store or the internet :-)...

And yeah, maps generate stories -- I tend to start with a map, and let my tiny people face whatever situations the terrain deals them.