How does negative gravitational work result in an increase in potential energy? I'm trying to untangle some confusion when it comes to understanding work.
Suppose a rocket is moving upwards (in the opposite direction to the force of gravity), with a uniform velocity.
For simplicity, let's assume the mass of the rocket is tiny relative to that of the earth, and define the system as comprising only the rocket.
The combined total work done on the rocket, by engines and gravity, is zero, since there is no change in kinetic energy.
This result makes sense given the definition of the work energy theorem, which states that the work done on a system is equal to the change in kinetic energy of that system.
If we analyze the work done on the rocket by the engines alone, it is equal to the force of the engines (mass * gravity) multiplied by the displacement. 
The work done by gravity is the exact negative of the work done by the engines.  We can derive this work done by gravity in two ways: 


*

*The total work is 0, and therefore the work of gravity must be equal and opposite to the work done by the engines.

*Work is defined as the force multiplied by the displacement in the direction of the force, and the force of gravity is $\left[\text{mass}\right]{\times}\left[\text{gravity}\right]$, i.e. $mg$, and the displacement is opposite to the direction of this force, so work done by gravity is $-mg \, {\Delta x}.$
This is where I now get confused:
I've often seen it stated that the negative work done by gravity, in this situation, is precisely what is causing the rocket to gain potential energy. In here, for example:

The gravitational force that did negative work on the ball and decreased its KE has in the process increased the PE of the ball. Thus negative work (W1) has resulted in positive change in PE. 

Or, from here:

The fact that these two cancel out (Wnet=Wyou+Wgrav=0) means that the kinetic energy of the object after being lifted is 0. So the work done by gravity went to sucking energy out of the object that you were adding, thereby converting it to gravitational potential energy.

This immediately strikes me as bizarre. I associate an increase in height with an increase in gravitational potential energy (as something goes higher, its potential energy also goes higher). Yet the force of gravity is acting downwards, and a downwards force will reduce the rate at which an object attains height. So if anything, isn't the work done by gravity contributing to a decrease in the rate at which the potential energy is increasing?
I understand that there's a bit of an irony here - the very thing that gives an object potential energy is gravity, and if you increase the gravitational force, you increase the gravitational potential energy. But on the other hand, the force of gravity reduces the rate at which an object attains height, and height is proportional to gravitational potential energy.
I'm very confused here - to me, it makes intuitive sense that, while yes, the gravitational field is what allows gravitational potential energy to exist, it is the force of the engines that is driving the upward motion, and therefore causally implicated in the rise in potential energy of the rocket. So why is it said that the work done by gravity (which is negative!) is what results in the increase in potential energy?
Indeed, from Wikipedia:

The amount of gravitational potential energy possessed by an elevated object is equal to the work done against gravity in lifting it.

While this doesn't logically imply that the work done against gravity (i.e. by the engine) is causally implicated in increasing the potential energy of the object, it surely suggests as much. And I can't help but come to that conclusion: without the engines, the potential energy of the rocket would remain at 0. With the engines, the potential energy increases!
 A: There's always confusion with this topic when it's not well explained. It's all inside "work-energy theorem", which says
$$\Delta E_k = W$$
But we'll make a distinction here: work done by conservative forces and work done by non conservative forces:
$$ \Delta E_k = W_C + W_{NC} $$
And now, we just call "minus potential energy" to the work done by conservative ones
$$W_{C}:= -\Delta E_p$$
We do this for convenience. We can do it, because a conservative force is such taht can be written as a substraction of a certain function $B$ like this:
$$W_C=B(\vec{x_f})-B(\vec{x_0}) $$
We just decide to define $E_p=-B$, so $W_{C}=-\Delta E_p$. We include that minus sign so that we can take it to the LHS:
$$ \Delta E_k = W_C + W_{NC} $$
$$ \Delta E_k = -\Delta E_p + W_{NC} $$
$$ \Delta E_k + \Delta E_p = W_{NC} $$
$$ \Delta E_m = W_{NC} $$
So the increment in mechanical energy is always equal to the work done by non-conservative forces. If there are no non-conservative forces, then $\Delta E_m=0$ and energy is conserved (that's why we call them like that.
(read it slowly and understand it well)

So, having this in mind, I think your confusion arises because of that famous "artificial" negative sign. 
There are many formulas, and it's typicall to have a mess. It's all about surnames:  $\Delta E_k = W_{Total}$, but $\Delta E_m=W_{NC}$. The subindices are the key.

The force of engines is non-conservative. Hence, their work contributes to total mechanical energy.
Gravity is conservative, so we can work with its potential energy.
If there is no increase of kinetic energy, that means
$0 + \Delta E_p = W_{NC}$
So engines are only increasing potential energy. But that means
$$-W_C = W_{NC}$$
Of course, if there's no gain in KE, no acceleration, there's equilibrium. The work of the engines is compensating the work of gravity.


*

*Negative work is always positive $\Delta E_p$, by definition.

*More altitude means more $E_p$, you are right. But here energy is not conserved (engines). Normally, increasing height would decrease $E_k$, but we're adding work so taht $E_k$ stays constant. 

*$\Delta E_k=0$ implies $W_{Total}=0$. That means gravity is making negative work, and engines are doing positive work (equilibrium). The thing is that potential energy variation is minus gravity's work.

A: Let's consider a simpler example with a mass at the end of an anchored weightless spring.
As the mass oscillates at the free end of the spring, there is a continuous conversion between kinetic and potential energies. The kinetic energy here belongs to the mass, while the potential energy belongs to the spring.  
As the spring stretches, it performs a negative work on the mass, since the mass is moving in the direction opposite to the force applied by the spring. 
We can say that the kinetic energy of the mass (the only energy it may have) is deceasing because the spring performs a negative work on it, while the potential energy of the spring is increasing because it performs a negative work on the mass.
We can also turn it around and say that the mass performs a positive work on the spring (since the direction of the force the mass applies to the spring coincides with the direction of stretching) and, as a result, the potential energy of the spring increases, while the kinetic energy of the mass is decreasing (is being spent).  
All the above seems consistent: in all cases the energy flows in the direction of the work.
Alternatively, we could treat the spring and the mass as one entity and claim that, since no external forces perform any work on it (assuming that the fixed end of the spring  is not moving), its total energy is not changing and all energy transitions are internal.
In case of a ball moving up and down in the gravitational field of the Earth, we may decide that the potential, as well as the kinetic, energy belongs to the ball, in which case any work, positive or negative, done by the Earth on the ball won't make any changes in the total energy of the ball, which is a contradiction.
On the other hand, we can decide that the potential energy belongs to the gravitational field, in which case the energy transitions would be similar to the case of the spring and the mass and there would be no contradictions. I'll let the experts decide whether this approach is justifiable, but it appears to be helpful.
We could also treat the ball and the Earth as one entity and consider all energy transitions internal to that entity.
A: It is not true that without the engines the potential would remain at zero: if the rocket is moving and you turn off the engines it will keep moving, gaining potential energy and losing potential energy.
Perhaps one way to think about it is that since the work done by gravity is negative, gravity is sucking kinetic energy out of the rocket. Instead of thinking that this kinetic energy just disappears, we can imagine that as it is being drained out of the rocket it is being put into a potential energy reservoir. This negative work does contribute to making potential energy increase more slowly, but a bit indirectly: it removes kinetic energy, which makes the rocket slow down.
Wikipedia's statement is a little misleading. Think of launching a cannon ball from a cannon: we do a lot of work all at once at the beginning, and then the potential energy increases while the cannon ball is going up, when the initial work is already over. What the statement means is that the potential energy is the work you would have to do if you lifted the body from the ground to some height, with zero kinetic energy at the beginning and at the end, with some hypothetical steady force. It's an imaginary scenario, which serves as a definition of potential energy but doesn't actually have to correspond to your specific situation.
A: 
For simplicity, let's assume the mass of the rocket is tiny relative to that of the earth, and define the system as comprising only the rocket.

This makes an explanation a little easier as one then only needs to consider the work done on the rocket when one remembers that gravitational potential energy is actually stored in the rocket & Earth system rather than just in the rocket alone.
The gravitational potential energy of the rocket & Earth system increases when the separation between the rocket and the Earth increases. 
To further simplify things assume that there is an external force acting on the rocket $F_{\rm external}$ which is equal in magnitude and opposite direction to the gravitational attraction on the rocket due to the Earth $F_{\rm gravitation}$.

Suppose a rocket is moving upwards (in the opposite direction to the
  force of gravity), with a uniform velocity.  

This means that the net force on the rocket is zero, the net work done on the rocket is zero and the kinetic energy of the rocket stays constant.  
In terms of work done  
$W_{\rm external} + W_{\rm gravitation} = 0 \Rightarrow W_{\rm external} = - W_{\rm gravitation}$

And I can't help but come to that conclusion: without the engines, the potential energy of the rocket would remain at 0. With the engines, the potential energy increases!  

Instead of "without the engines the potential energy of the rocket would remain at $0$" I think that you meant to write "without the engines the change in the potential energy of the rocket would remain at $0$" but even that statement cannot be true as there is a net downward force on the rocket due to the gravitational attraction of the Earth so the rocket cannot hover at a fixed height above the Earth.
However, the statement "With the engines, the potential energy increases!" is correct. 
When the external force does work in increasing the distance between the rocket and the Earth then the gravitational potential energy of the rocket & Earth system increases.  
$W_{\rm external} = mg \Delta h$ where $\Delta h$ is the increase in height of the rocket and assuming that the gravitational field strength $g$ is constant.  
Because $W_{\rm external} = - W_{\rm gravitation}$ the equation for the gain in gravitational potential energy can be written as
$-W_{\rm gravitational} = mg \Delta h$ with the numerical value of the left hand side of the equation being positive because $W_{\rm gravitational}$ is negative.
$W_{\rm gravitational}$ is negative because the displacement (upwards) is in the opposite direction to the gravitational force (downwards) so the dot product of the force and the displacement is negative.
