Well, if you're not even at the point where you think the guides are helpful yet, as one n00b to another, I can at least answer your specific questions:
(1) Use whatever music you like, which you think goes well with the anime footage you want to use. Or go the reverse direction and start with the music and search out footage that goes with it. Come up with a concept you think is worth your time, and go from there. Combining the music and images is where you get to use your creativity, and the sky's the limit. Sometimes very unlilkely combinations can give great results. Take a look at the videos listed in the Theory guides or the top star scale for examples.
(2) Get started by reading the guides, or at least skimming them. Then collect some source footage and music and start learning how to use an editing program
(3) You can certainly put together AMVs using Windows Movie Maker. Some people on non-windows platforms may have trouble viewing them, and most people eventually find that they want a more powerful tool, but plenty of AMVs have been made using it.
(4) You can see reviews of various commercial editors at
http://www.videoforums.co.uk/guide-videdit-16.htm or
http://www.videoguys.com/RT5.html. It shouldn't be difficult to find places to buy them.
<i>"Tamago no kara wo yabureneba hinatori wa umarezu ni shin de yuku. Warewa ga hina da. Tamago wa sekai da. Sekai no kara wo yaburaneba warera wa umarezu ni shin de yuku. Sekai no kara wo hakai se yo. Sekai wo kakumei suru tame ni!"</i>