Just checked out the video and the making of graphic. While there's any number of programs that can pull this off, it's quite likely that the creator used After Effects. Basically its just a matter of rotoscoping (or masking. However you like to say it) one footage, then putting it on top of another piece of footage. Now, that's a very simplified way of putting it, since there's way more going on here than just that. He's also color correcting, compositing using other procedurally generated effects or textures, etc. But, the #1 thing to be aware of is the creativity. To be honest, the technical side of it, while impressive, is something anybody can learn to do. The hard part is actually deciding "what do I really want/need this shot to look like to get my story/tone/mood/etc. across?" If the video didn't have those things going on, then it would fall flat. And the fact that many people would be able to watch the video and just assume that most of it was all from one anime, is a mark of success.
Ask Brad an After Effects Question! - Forum - Site