Echoing Bashar, play around with the editing tools and filters/effects on some stock footage first to open your mind to what you have at your disposal. After that, start off with an easy idea, preferably something comical that isn't too upbeat.
A basic skill would be syncing an action to the beat of the song. You can have a "bleh" concept but really good cuts. However, you can have a good idea in your head, but totally shot to hell if the clips are all over the place.
When you hear a song, put it on repeat and think of the first anime that pops into your head. When you got one, keep listening to the song and reflect on all the scenes you remember from the anime and try to envision them being played at the same time as your song.
Try to have a focus. Using multiple anime on your first video can be hard. Tell us a story. It doesn't have to be a long, intricate movie, but at least show us "why are these swordsman fighting?" or "how did these two lovers fall in love?"
Almost as hard as fighting a Holy Paladin.