I am not sure what class of surfaces or topological spaces this is a theorem for but it should at least include the plane, circle, sphere and torus (hopefully also the Klein bottle) - so part of the question is what class of surfaces to consider:
Given a fixed base point consider every path in some homotopy class. How can one prove that a shortest path exists and that it is a geodesic?