Basic misunderstanding of the theorema egregium The theorema egregium demonstrates that the Gaussian curvature, $K$, is an intrinsic property. What I think this means is that if you know the metric corresponding to the surface, then you can compute the Gaussian curvature. Equivalently, two isometric surfaces have the same curvature.
Gauss gave an explicit formula for $K$ which only depends on $E,F,G$ and their derivatives, where $E,F,G$ are the matrix elements of the metric. Because of the independence of the embedding, it makes sense to study surfaces in their own right, i.e. not being embedded into $\mathbb{R}^3$, right?
What I don't understand is that $E,F,G$ are coming from the metric upstairs. How could someone living on this surface calculate the curvature using this formula? That would mean they know $E,F,G$ which would mean they know the embedding, which means they know that there exists some higher dimensional space. 
A person living on a surface doesn't know of the third dimension. To them, their world is a 2 dimensional plane, right? So to them they would always measure distance the standard way, using $dx^2+dy^2$. This person could perhaps calculate the interior angles of a triangle and see that the sum is not $180$, but that's not using the formula for $K$. 
It seems that a person in $\mathbb{R}^3$ is calculating the induced metric and saying this is the metric on the surface. But a person on the surface thinks they live in $\mathbb{R}^2$ and so are using a metric that has no dependence on the $z$-coordinate. 
How does a person on the surface calculate the Gaussian curvature of their world?
 A: To answer your last question about calculating the Gaussian curvature of a surface: One way is discussed on Wikipedia. The idea is to use the "angle excess formula," which states that if $\Delta$ is a geodesic triangle on a surface with angles $\alpha$, $\beta$, and $\gamma$, $K$ is the Gaussian curvature, and $dA$ is the area form, then
$$ \int_\Delta K \, dA  =  \alpha + \beta + \gamma - \pi.$$
This means that the Gaussian curvature $K(p)$ at a point $p$ can be computed as the limit of the angle excess of $\Delta$ divided by the area of $\Delta$, where the limit is taken over geodesic triangles $\Delta$ containing $p$, as the area of $\Delta$ tends to $0$. (I suppose the continuity of $K$ is used here.)
I don't know whether that's a satisyfing answer (or whether a hypothetical surface-dweller could actually perform an experiment to compute such a limit). There is folklore about Gauss measuring the angles of the triangle formed by three mountains in Germany, but after reading this article (of unknown trustworthiness), it's unclear to me what he was trying to accomplish.
