1. I actually had not seen any. I was a sappy eighth grader and thought, "wow, these scenes from Tenchi in Tokyo would go really well with Show Me The Meaning of Being Lonely by the Backstreet Boys! I wonder if I could take footage and put it to the music... has anyone done that?" (yes, this was back in 2000 or 2001 or so.) Then, some guy my dad worked with had a son who was into anime. The guy burned me a data CD full of some old classic AMVs and I got really excited realizing that people actually DO make those.
2. Started making them very shortly after that. I made a really crappy one to "She Bangs" by Ricky Martin (this was before William Hung, even) with Aeka from Tenchi Muyo... it was good considering my limited resources, but. I basically used some random software that my uncle happened to put on the computer while transferring pictures (it was part of some program package) and I ended up editing that way. Pain in the ass, it wasn't timeline format (or I hadn't figured out how to view it that way), and some of my source footage was real media so I paused it every split second and did screen captures for lots of the frames.
Luckily, since then, I've gotten my hands on better resources..... ^^; Shortly after that I got some VHS-to-computer software and edited the Backstreet Boys video I'd imagined first. It's on my first account, WashuuChan12, to which I forgot the password ages ago and have changed my email. When I got my laptop I started using WMM, continued using WMM when I got a desktop (the one good thing about Vista is that the WMM is soooo much better) and then my fiancé bought me Sony Vegas Platinum.

So I've been using that.