This answers the "how", but not the "where". Since energy itself has mass, we would expect the potential energy to carry mass as well; and that that mass/energy should be concentrated in some region of space.
Potential energy is a property of a system rather than an actual physical thing. It's not energy an object has, it's energy an object potentially has relatively speaking. And it's relative to whatever you use as your reference point in your system.
>Since energy itself has mass
Energy doesn't have mass. It is equivalent to mass.
The answer to the question of 'where' is the underlying (non-gravitational) physical field (and in particular the electromagnetic field, which is long-range, whereas the nuclear fields normally get folded into mass terms). The case of gravitational potential energy is a bit more subtle: It's excluded from the stress-energy-momentum source term of the Einstein equations, and there's no expression for a gravitational stress tensor (though there are pseudo-tensorial approaches).
Like others have mentioned, you need to look at the two planets and the spaceship as a system together. The gravitational potential energy you gain from raising a spaceship out of one planet's gravity is equal to the energy you spend getting it out of that planet's gravity well (neglecting efficiencies).
While the trip from Planet A to Planet B might seemingly "gain" you extra potential energy because of the differences in gravity wells. The reverse trip of going from Planet B to Planet A will reverse that "extra" potential energy you gained as it's more costly to get out of Planet B's gravity well.
As so, there's no "extra" or created energy within the system. As for where energy is stored, it's simply stored as gravitational potential energy.