AMVs itself is pretty broad as everyone do them differently. Each program has its special pluses.
For the video as a whole, Sony Vegas is an excellent choice for videos. You can edit videos and make video clip transitions very easily. Sony Vegas also allows one to layer videos on videos and such. For the normal AMV where clips are put together to make a short video, Sony Vegas is the standard video editor. Windows Movie Maker is a valid option as it does what's needed by putting videos together. However, Windows Movie Maker is bare bones. You cannot do fine timing, which is what makes the difference when it comes to music videos. The ability to time each syllable of the lyrics, fancy transitions, video overlay over video, etc. But going deep into animation such as putting in your own character or sparkly what not, I would use Adobe After Effects.
After Effects is incredibly useful on small animations or multiple animations that go into each video. Adobe After Effects is where you would sink in an incredible amount of hours to make an incredible piece of video. Also note that After Effects can be used with Photoshop and Illustrator to a good degree. Of course, there are other video programs, but I would say that these two, Sony Vegas and Adobe Aftereffects, are the main. Let's say your making an AMV which involves a person looking into the TV. Aftereffects is good for this cause you can replace what's in the TV in the video and make it look much more natural by adding in more filters and special effects. While it isn't related to AMV, check out what freddiew does on his
youtube channel with the power of AfterEffects. A good reference for good AMVs can also be Nostromo.
I have also used Aegisub to make texts on screen in a very fancy way in videos. This itself requires "programming" the words on the screen but may prove useful if you want lyrics on the video or simply want words to look nice and easily animated such as on that video screen in the earlier example.
Don't forget that video quality is important, too. The video pieces you use should be RAW videos that are a decent resolution. If you use a mix of After Effects and Vegas, you should use the after effects to make the special parts of the video and encode the parts uncompressed. You can then load them into Vegas, edit the video as a whole and then use Vegas's video encoder for the final cut. However, I personally would recommend to use Vegas's video encoder to make another uncompressed video of the finished video and then compress the video with a more advanced video encoder like MeGUI or handbrake or whatnot. I won't really get into video compression as that itself needs a whole encyclopedia for. Just make sure that it's h264(with the right settings) and aac if you want to be able to view the video on game consoles.