Are you asking how to make shitty music like in that video?
I have to say...I don't get why The Mars Volta or similar style bands get so many props in the media...??? I've seen a few appearances by them...and they always sounded like that.
Yeah...there's some of that "Mothers of Invention" flavor (very little)...but with a BIG difference in musicianship, execution and ultimate intent.
Mind you, I'm not just into beautiful, melodic styles...but that is just a lot of noise.
Now....back to the original question...
That video of The Mars Volta has nothing to do with "scoring" a video...that's just a videotaped performance.
There's nothing difficult about that...just put up a camera during your performance.

If you want better audio than what the camera can capture...then recording the audio at the same time with better audio gear...and then just swap the audio tracks using something like Sony Vegas, which is a video editor.
That's exactly what I'm doing right now. I've recorded some guitar clips of me playing, but I don't care for the quality of the audio from the camera mic...so I simultaneously also recorded audio into my DAW...and now I will swap audio files in Vegas.
If you are talking about a typical MTV-style music video production....that's a lot more work and planning, though how involved can go from very minimal to something like shooting a full tilt short movie.