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?
Best Answer
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.