Nothing is actually stored. (You will not find anything "in" the body :) )
The increase of potential energy means in this case that there is a force (of gravity) acting on a body, and the body's movement away from the source of this force increases the distance the body can p o t e n t i a l l y travel under the influence of this force. So if the body is eventually allowed to free fall, with every moment of the accelerated motion of this body toward the source of gravity its energy will be increasing according to the equation
Acceleration means the velocity will be increasing with every moment of the body's travel. Therefore, the further the body gets from the source of gravity, the longer its movement will be, so the greater the velocity it will attain, and therefore the greater the kinetic energy it will actually acquire.
In short, moving away from the source of acceleration increases the potential velocity a body can finally achieve on its way back (to the source of acceleration). That's all.
(Also, the movement away from the source of gravitation requires a force to counteract the force of gravity, which means expenditure of energy. Letting the body go allows it to acquire energy (back) - from its movement toward the source of gravity.)
To maintain consistence with the other question you referred to:
A body must do work against an opposing force to continue motion.
This is a statement that I have found many times. But what is the reason behind it ? Suppose $F_1$ is acting on a body to accelerate it (to increase the K.E). Then another force $F_2$ less than the former acts on the body in the opposite direction. So, according to the above statement, the body must have to lose energy. But why will the body lose energy?
I will give you a different answer than people did there, but perhaps a more straightforward one.
Why will the body loose energy? OK, how was its energy expressed? Before another force begun to oppose, the body's energy was constantly increasing as its kinetic energy equals to $mv^2/2$, and $v$ was constantly increasing, because according to this law by Newton: $F=ma$ the force was causing an acceleration. Now, when the opposing force appeared, the resultant force working on the body was $F_1-F_2$. This means that the acceleration of the body must have decreased, which means its velocity must have decreased, and which means its kinetic energy must have decreased. Hence the loss of energy.
OK, now let's go back to your initial statement: "A body must do work against opposing force to maintain motion". According to Newton, again, a body is in (uniform) motion when there is no (resultant) force working on it. You do need a force as an impetus to body's motion from a stationary state, but in order to maintain (uniform) motion you do not need it anymore. Now, if this body in uniform motion encounters an opposing force ($F_2$), this force will cause an acceleration of the body in the opposite direction - so first it will decelerate the body to a halt, and then accelerate it in the opposite direction. If you, however, want to counteract it and maintain the initial motion you need to apply another force ($F_2$) to the body. Obviously, this (and any) force needs time to exert its influence, which translates into distance ($s$), so given the equation for work: $W=Fs$ we can see there must be work done to maintain the motion.