How do I overlay a photo of a face over a character on a video?
Track the element over which you want to overlay the image.

With the tracker selected got to the Solve tab and in the Geometry dropdown, click on Link Empty to Track.



That will create an empty that is parented to the camera and moves with the movement of the tracked element.



Add the picture of you want to overlay one using Import Images as Planes



Parent it to the empty: select the plane with the image and then while pressing Shift select also the empty and press Ctrl P. 

Now your image will move with the empty.



You might want to enable the video clip as background image at this point to see the have a reference of the movement.





For elements that change size or perspective you create a Plane Track tracking four points of the video. The instructions on how to do that are here:

http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.69/Motion_Tracker

and an excellent tutorial by Sebastian König here

When you are done adding all the elements you want, you can render the scene using a node setup like this where you add your scene to the background video.

 

I'm just going to deal with the tracking part. The texturing should be a different post since it is a different question, and there is enough information  here and here on how to pull that off.