How can gravitational potential energy be stored in empty space? If I pick up a rock and set it on a ledge above my head, I do work in the process. The work I do is termed "potential energy". We know how to recover the energy (i.e. let it fall back to earth). 
However, while resting above the surface the energy is said to be "stored in the gravitational field", presumably meaning the space between the elevated rock and earth. Suppose we perform this experiment on the moon where we know the space between the elevated rock and surface consists of an empty vacuum of space which contains absolutely nothing. How can empty space store energy? That is, how can "nothing" have any properties whatsoever?    
 A: You're right: potential energy, as taught in introductory physics courses, is a "cheat". 
On a fundamental level, there's no such thing -- there's only energy stored in fields. Since field descriptions are more complicated, your course glossed over it by calling the field energy "potential energy". It's totally fine for solving problems, since the bookkeeping is the same, but it can be confusing if you ask where the energy actually is. This is a big logical hole in intro courses.
In your case, the energy is stored in the gravitational field between the two objects. It's totally analogous to how energy is stored in the electric field between two charges. Here, the gravitational field is the metric tensor $g_{\mu\nu}$ and the presence of the masses perturbs it from the flat metric $\eta_{\mu\nu}$. 
This gravitational field is not "nothing", even if there are no matter particles there. Its value, energy density, momentum density, etc. can all be measured and observed. In fact, from a modern perspective, there are only fields. Even the rock in your example is just a complicated excitation of the electron, quark, gluon, etc. quantum fields.
A: Gravitational Potential Energy is the difference in the total energy of a mass between two points in space as a direct consequence of the difference in the length of a metre between the two locations.
In other words, it is a direct result of gravitational length contraction.
The total energy of a mass can be expressed as $$E=mc^2$$
But it is also Force × Distance
I.e. it's the distance that a 1N force can be applied by the mass if all of its energy is released..
During free fall, the unit of distance decreases at a rate of $$g/c^2$$ wrt  distance fallen.
Therefore the total energy of a mass reduces at a rate of $$mc^2g/c^2$$
Or $$mg$$ wrt distance fallen due to gravitational length contraction.
The change in total energy over a given change in height, mgh (or more generally over a given change in gravitational potential) is what we call Gravitational Potential Energy.
Gravitational length contraction is the result of a reduction in the wavelength of light between the two locations.
