I suppose they use some kind of heuristic to generate depth information from the 2D image, and then render the resullting scene in a 3D environment, creating the illusion of depth. I am pretty sure this is nontrivial to do.

Or maybe something else. Can you show a few examples of 2D photographs and their resulting 3D avatar?

I think first you need good face-detection algorithm that should work from any angle (from frontal to profile) and also determine the functional parts of face (eyes, moth, nose, ears, hair...)
Then you need good deformable face model that can be morphed into most realistic human faces using small fixed number of morph targets.
Then you have standard optimization problem of finding specific face morph (plus hairstyle + skin color + lighting + ...) that will give the closest result to your photograph. Although I am pretty sure that real algorithms use many shortcuts because finding the global optimum is too difficult.