There's a bunch of ways to do these, you'll probably want to look into Adobe After Effects. My favorite tutorial site for AE is VideoCopilot
Then you need to overlay the AE Project on top of your video. For some things you may need to do 3D Modeling and Animation in a suite like Maya or 3DMax as well. It kinda depends on what exactly you're going for.
Found this which you might find interesting as well, shows a little behind the scenes and you can see just how much production and people are involved in something like this: http://www.blind.com/work/project/windowsphone7/
A better StackExchange for Video is aptly called video.stackexchange.comvideo.stackexchange.com