... I usually start (uh, in terms of ideas and finished videos) with the song, when visuals will come into my head just as I listen - or a lyric or a sound will remind me of something I've seen.
For example: I was listening to "Drama!", while waiting for a ride after work one day. Since I had played FF8 lately, the line "Your shame is neverending, just one psychological drama after another" reminded me of all the melodrama in that game. Over time that evolved into my second (and badly edited

) video.
Almost every other idea I've had has gone like that, song first, visuals just suggested by my wandering mind.
The exception to this would be "Sea of Stars", where I was watching the footage without sound and thought, "I need a nice floating song to go with this..."
Anyhow, I would pick a song, if that's the case, that first of all fits the tone or mood of the idea I want to present. Thoughtful, angry, whatever. Then, the lyrics - unless they're not very important in the song either - have to match, or at least be warped around in meaning to fit the series.
Title is irrelevant to me, though it can be useful sometimes in titling the video when it's done.

Most important are sound/mood and lyrics.