When chemical energy is released mass is reduced, if only by a negligible amount. Presumably that's true for all energy. And presumably that works in reverse as well: storing energy involves an increase in mass. It seems to follow that moving some object against a gravitational gradient, increases the mass of the object — potential energy is being stored. Somehow that's difficult to understand. Is it really true?
[Physics] storing energy (as mass)
energygeneral-relativitymassmass-energypotential energy
Best Answer
From your question and your comments on Google+, it appears you think there is a problem with having the increased energy stored in the gravitational field since the gravitational field is really just curved space-time. That is not a problem, curved space time does have an energy density and in fact can cause additional curvature of space time. That is why general relativity is much more difficult than Newtonian gravity or electrostatics - the equations of general relativity are non-linear exactly because the energy stored in the curvature of space-time causes additional curvature of space-time.
In fact, John Archibald Wheeler conceived of the possibility of a gravitationally bound object that is only made from gravitational waves. From Wikipedia:
It is believed that a geon could be formed, but that the "particle" would dissipate due to gravitational waves that escape from the object, thereby reducing it's mass.
So, to get back to your question, two different configurations of particles that had the same total rest mass but different gravitational fields would, indeed, have different overall total mass/energies due to the different amount of energy stored in the differently curved space-times around the objects.