Combinatorial embedding of a graph
This is really less about graph per se and more about topology. A combinatorial embedding defines a 2-manifold, a topological space in which every point has a neighborhood homeomorphic to a 2-dimensional open disk: the embedding allows a face to be defined, and we can define a topological space by choosing a disk for each face and gluing them together along the graph edges. A well known theorem in topology (called the classification of 2-manifolds) tells us exactly which 2-manifolds are possible, and they are all distinguishable from each other either by whether they are orientable or whether they have the same Euler characteristic (or both) — see http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdf for some reasonable lecture notes on this subject, that include the proof you're asking for. There are no other 2-manifolds in this classification that have the same Euler characteristic as the sphere, so if you calculate the Euler characteristic and find that it matches the formula for a sphere, you know your embedding must be onto a sphere.

Finding an embedding with actual geometric coordinates in the plane, once you have a planar combinatorial embedding, is not entirely trivial but can be done e.g. using the theory of Schnyder woods. I have some lecture notes on this at http://www.ics.uci.edu/~eppstein/gina/schnyder/ for instance.