Hey there! I'm pretty new to this myself, but I've made progress. :) And you can too!
Getting Advance Map is definitely the first step. I found a really great tutorial when I first started, but I can't find it at the moment. If you'd like, I can PM you the copy that I pasted into Word so that I could highlight important sections.
I'd say that proper planning is essential. I played around with a test ROM at first, but I didn't really start learning stuff until I actually started on my actual ROM hack. It also helps that I accidentally planned it out so that there are less changes in the beginning; so the difficulty in hacking is gradually increasing as a go along. X) You may be different though; this is just what worked for me personally. I did a play-through of the game on an unhacked ROM and took notes throughout the whole thing, noting what I wanted to change. It's definitely made things easier for me.
If you're just looking to learn the bare minimum basics right now, I'd say John's suggestion is pretty good. Editing what Pokemon can appear is simple yet essential.
Oh, and don't try to hack Sapphire or Leaf Green. I've heard that they don't work with any tools. Ruby and Firered are usually recommended, and they're essentially the same thing as Sapphire/Leaf Green, but I'm hacking Emerald personally. I've heard people say that Emerald is more difficult, but I've yet to find any evidence of that.
Good luck! If you have any more questions, don't hesitate to ask! :)
EDIT: I found the guide! You can find it
here.