All we can really do is give you guidlines, because it's really up to you to be creative with your work. It's best to use what inspires you.
I suggest using an anime that you have on DVD or VHS, or one you can rent from a rental store (downloading fansubs or taking from other's videos makes the video have minimal quality). Plus, usually if you own it you like it, and I would say make a video to an anime you like. But keep in mind we are all sick of DBZ videos.
Now find a song that you love (because usually you will like to watch your videos over and over if it's to a song you like rather than to a song you don't), and try to pick one that hasn't been used much or at all (we've all seen a little too much of Linkin Park and System of a Down), then put it to an anime you think suits it. Try to connect the song to the series.
Now, plan until you know exactly what's going to go where (I would read
Phade's Guide for a good way to approach creating your AMV, especially if you're new to this).
If you want to make an original video, look at the Most Used Music section on your member main page to get a good idea on what kind of music we see way too much.
Then have lots of fun editing, and don't worry if it doesn't look the greatest because most first videos kinda suck. I would say go with what inspires you, because that's the best way to have fun making a vid.
If you want some suggestions...
Trigun is an awesome anime (even though there are about 300 of them), and we have sadly few videos that are any good, so if you're going to spend a long time on this vid I'd like to see some more good vids from this series^_^
And I'd say go with one of your favorite songs on this one. Our taste in music might not be the same as yours.
But tell me what kind of anime you own, and I could say what I think could work for this vid if you want^_^