Ok Go "WTF?" Music video - How?

[Supaman22]

Ok, so immediately after seeing this video http://www.youtube.com/watch?v=12zJw9varYE I wanted to do something similar. I did a google search and came up with this http://blog.makezine.com/archive/2010/01/the_okgo_wtf_effect.html but the application he made is just ok. First, you have to play the song "WTF?" to use it and second, the video doesnt look nearly as good as the OK Go version. (do I need a greenscreen?)

Anyway, is there a way that I can do this using software on a mac?

Thanks