What program do you need to do the following?

This just looks like the age-old method of 'stop motion', where animation is done frame-by-frame. Pretty much any popular video editing program can be toyed with to get this result, but for more advanced works, you might have to look around for something specialized. Just do a google search for 'stop motion program', and see what gets returned.

Regular Still-Shot Camera

If you notice in the "movie" there are parts where the paper man's feet are taped to the table. also, pay attention to how much the perspective jumps around between frames. It would be my *educated* guess that it's a compliation of many photos into a video.

digital camera, windows movie maker