I really depends on the mood you are going for in the AMV. I can honestly say, that most of the time a song with a good beat or a really 'sad' song can work really good. (Most songs average beats around 2, 3, 4, 5, 6, 10, 12, 20, and 30 seconds.) What this means: You will want to try to get your video as close as possible to match with the beat of the music. If you want and example, check out Atom X's amazing FF9 tribute done with 'In The End' by Linkin Park. That's what I mean. His work is some of the best I have ever seen. (Averaged beats is also known in the AMV world as 'Synchronization'.)
Here is a list of bands and songs that are good to use:
Linkin Park
(Although certain songs have been done way too much. If you really wanna make something fresh, use a song that hasn't really been used. Like 'Runaway' instead of 'In the End', 'Somewhere I Belong', or 'Numb'.
Nickelback
Evanessence
Breaking Benjamin
Greenday
Saliva
System of a Down
Creed
Crossfade
Taproot
Trapt
Papa Roach
Another tip: DON'T use 'fillers'. This really downgrades your video. Trust me. Fillers are ok, to a certain point. But make sure it is related to whatever is going on in the video, and as long as it isn't used to fill more than about 5-10 seconds of video. (The viewer will lose interest and may stop watching, all together.)
Use 'decent' video/audio sources.
This means, go get the dvd of what ever anime you want to copy. Get the highest quality mp3 you can of the song. (I preferre to buy the cd and rip it into 320kb/s mp3s.)
Also, when saving a movie, try to save it at the highest possible quality settings. (Takes up lots of harddrive space.) But make sure the file is small enough to burn to a single cd, or preferrably: DVD.
(And take time to learn how to rip your movie to SVCD or DVD.)
If you don't like how one scene is, change it up some. Do something different, and experiment. Sometimes, it just works out by itself. (Although don't do it often, as it will cause the viewer to think that it is random and chaotic.)
Oh, and have fun. That's pretty much the biggest rule. You won't have a good video, unless you are having fun making it.
Here is an AMV I have worked on. It is still a WIP (work in progress), as I haven't really had the time to complete it.
(Took me about a day to make the intro, and 2 days to remaster it into the current version. I need to get a DVD source 'Wandering Samurai X: Trust&Betrayl' for the video, though. Note*: The part at the beggining that skips was left intentionally. It was on purpose, just thought it looked a little cool.)
Intro:
http://www.freespaces.com/omega/socold_kenshin_teaser_trailer.wmv
Main:
http://www.freespaces.com/omega/kenshin_wip.wmv
Website:
http://freespaces.com/omega/kenshin.html