Potential Energy and Work My physics textbook says when a rock is lifted gravity does negative work and increases the gravitational potential energy. My understanding of negative work implies energy is being removed when an object undergoes negative work.
Another force must have been applied to move the rock in the first place and this seems like where the potential energy is coming from and the negative work is gravity slowing the rock back to stationary.
Am I misunderstanding something?
 A: 
My physics textbook says when a rock is lifted gravity does negative work and increases the gravitational potential energy.  

The problem with reading this statement in isolation is that it is ambiguous.  
The first thing which is not clear is the system which is being considered.
Is it the rock alone or the rock & the Earth together?
The implication from the statement is that the system is the rock & the Earth as the rock by itself cannot have gravitational potential energy whereas the rock & the Earth can.  
This is an important distinction because for the rock system the gravitational attraction on the rock due to the Earth is an external force whereas for the rock & Earth system the gravitational attraction on the rock due to the Earth is an internal force with its Newton third law pair being the gravitational attraction on the Earth due to the rock.  
To simplify matters consider what happens to a rock with is moving upwards with some kinetic energy $K_{\rm start}$ and then some time later it has a kinetic energy $K_{\rm finish}$.  

If the system is the rock alone then there is only one external force acting on the rock which is a downward force, the gravitational attraction on the rock due to the Earth $W$.
If the rock has moved up a distance $h$ then the work done on the rock by the gravitational force is $-W\,h$ with the minus sign being there because the displacement of the rock upwards is in the opposite direction to the downward external force on the rock.
So this is your "negative work done (on the rock system) by gravity".
Now using the work-energy theorem gives $-Wh = K_{\rm finish}- K_{\rm start}= \Delta K$ noting that the right-hand side of this equation will be negative.
Any other external force, eg your hand applying a force on the rock will contribute to the left-hand side (work done by an external force) of the equation so if you apply an upward force equal in magnitude to the weight of the rock then net work done will be zero and there will be no change in the kinetic energy of the rock.  

If the system is the rock & the Earth then there are no external forces acting on the system but there will be the two equal magnitude and opposite direction gravitational forces acting on the rock and the Earth.
Often an assumption is made that the mass of the Earth $m_{\rm Earth}$ is much, much greater than that of the rock $m_{\rm rock}$ but in this case I want to make that assumption later in the analysis but I do want to make an assumption that if the initial upward velocity of the rock was $v_{\rm rock}$ then the initial "downward" velocity of the Earth was $\dfrac{m_{\rm rock}}{m_{\rm Earth}}v_{\rm rock}$ ie the initial momentum of the whole system was zero. If the rock starts from the Earth's surface and the radius of the Earth is $r_{\rm Earth}$ then the initial gravitational potential energy of the system is $-\dfrac{Gm_{\rm Earth}m_{\rm rock}}{r_{\rm Earth}}$ and the final potential energy is $-\dfrac{Gm_{\rm Earth}m_{\rm rock}}{r_{\rm Earth}+h}$.
So the change in the potential energy of the system is $-\dfrac{Gm_{\rm Earth}m_{\rm rock}}{r_{\rm Earth}+h} -\left (-\dfrac{Gm_{\rm Earth}m_{\rm rock}}{r_{\rm Earth}}\right )= \dfrac {Gm_{\rm Earth} m_{\rm rock}}{r_{\rm Earth}}\dfrac{h}{r_{\rm Earth}+h}$ 
Now we can make the approximation $r_{\rm Earth} \gg h$ to approximate the change in gravitational potential energy to $\dfrac {Gm_{\rm Earth} m_{\rm rock}}{r^2_{\rm Earth}}h = Wh$ where $W$ is the weight of the rock.
So in the end there is a decrease in the total kinetic energy of two components of the system and a corresponding increase in the the gravitational potential energy of the system $Wh$.  
Although the internal forces acting on the Earth and the rock are of equal magnitude because the mass of the Earth is so much greater than that of the rock the internal force on the Earth will undergo a much smaller displacement than that of the rock so the work done by the internal force on the rock will be $-Wh$ the same as before.  
This illustrates that the change in potential energy is equal to minus the work done by the conservative internal forces.
A: One needs to carefully define the system.  Once done, we can distinguish between internal and external forces.  The definition of potential energy is $$\Delta U = -W_\mathrm{internal}$$   The work-kinetic energy theorem, which is what you are thinking of, is $$\Delta E = W_\mathrm{external}$$
Internal work is work done due to interactions between objects inside the system. Gravity is an internal force providing internal work. In the example of your textbook, the system comprises the Earth and the object.  Whatever is providing the force to lift the object (say, your hand) provides external work.
It would not be surprising if the book did not explicitly state what the system was to be.  That's a common problem in some introductory textbooks.
A: 
My understanding of negative work implies energy is being removed when an object undergoes negative work.

This is true for external or non-conservative forces doing work on the system. But we include potential energy as part of our total mechanical energy, which then removes the need to consider work done by gravity. In other words, you either account for work done by gravity and only consider kinetic energy, or you consider potential energy and don't worry explicitly about work done by gravity. I'll go into more depth below.
Let's say we don't think about potential energy. In other words, we just treat gravity as some external force doing work on our system. Then you are right, as we lift the rock gravity is taking energy out of the system through doing negative work. However, if we lift the rock at a constant velocity, it must be that we are doing an equal amount of positive work on the rock. The result is that there is no change in the energy of the rock, which is just kinetic energy in how we are deciding to account for energy. In this case we have $$W_{me}=-W_{grav}$$
Now let's say we do consider potential energy. Then the work we do on the rock goes into raising the potential energy of the rock. Once again, assuming the rock is moving at a constant velocity we end up with $$W_{me}=\Delta U_{grav}$$
Since we do the same amount of work in either case, it must be that $$W_{grav}=-\Delta U_{grav}$$
So we see that whenever gravity is doing negative work, it must be that the potential energy is increasing. But keep in mind that the force supplied by our hand is not required for this to take place. If we were to throw the rock upwards then while it is moving upwards after the release the potential energy would still be increasing, but in this case its kinetic energy would be decreasing.
This goes to show that potential energy (at least in Newtonian mechanics) is really just an efficient book keeping device. Instead of finding the work done by conservative forces we can instead consider changes in potential energies. This becomes very useful when our conservative forces are not constant over the path of the object. 
All of this is why you usually see energy conservation typically written as
$$\Delta E=\Delta K+\Delta U=W_{ext}$$
which just means that a negative external work does lead to a loss in energy. But by including potential energy you have included gravity as internal work, and thus work done by gravity does nothing to change the total mechanical energy $E$ of the system.
A: You write:

Another force must have been applied to move the rock in the first
  place

To address this objection let me first shift to a case where there is only a single force.
My favorite example is Halley's comet.  As it moves to its perihelion the gravitational force is doing work, increasing the velocity of the comet. Then, on the journey from perihelion to aphelion, the gravitational force is decreasing the velocity of the comet. 
We have acknowledged that it makes sense to describe increasing the kinetic energy in terms of doing work. The outward journey is in a sense the inverse of the inward journey. The gravitational force is the only force that is around, so whatever happens must be attributed to the gravitational force. So: to grant the idea of work being done includes the idea that on the outward journey the gravitational force is doing negative work.
This concept of 'doing negative work' is not exclusive to cases where there is only a single force at play. It is a valid concept in itself, therefore it is in all cases a valid concept.
Now to the case that you are asking about.
If you are in an elevator the floor of the elevator cabin is exerting a force on you, lifting you up. Now you have two options: you can describe the increase in height as a case of the elevator doing positive work, but you can equivalently describe the case as gravity doing negative work. Those two are the same thing. The only thing that you need to be careful about that you don't count the same work twice.
A: When a rock (your object) is lifted, gravity will certainly do work (negative work). 
There is a potential energy change. Where does it come from? How? 
From the earth. Earth has mass, and so it can attract the rock. According to $-GmM/R$ where M and R are the respective mass and radius of the earth, there is a energy change. An increase. In fact the potential energy change is $-GmM/(R+h)+GmM/R >0$. 
The way we derived it was using the fact that the work done by the force is negative of the potential energy change. If gravity performed negative work, it has increased the potential energy of that object. 
Now, addressing your doubt as the negative work removing energy is ambiguous as well. For an object going up in the presence of the earth, the kinetic energy goes down, but the potential energy goes up. 

Another force must have been applied to move the rock in the first place and this seems like where the potential energy is coming from and the negative work is gravity slowing the rock back to stationary.

Gravity is the reason why there is potential energy change. Not because of the force given by the person. You are right only when it comes to the potential energy change. The energy change because of the external force is higher than it would have if the object has no external forces acting on it.
A: The textbook is only talking about energy, and that $$U_{before}-U_{after}=W$$ where $U$ is potential energy and $W$ is work. In the book's example, $U_{after}$ is more than $U_{before}$ since the rock was moved away from Earth, so $W$ is negative. This is called the Work-Energy Theorem (there they talk about kientic energy, not potential, but the idea is the same).
Note that we don't care about the motion of the rock at all! It could go straight up in the shortest path possible and end up at rest a few metres above Earth. Or it could travel to Mars then Alpha Centauri and back to a few metres above the Earth (at rest again, we don't want to worry about kinetic energy). In either case, the above equation would hold! The important part is that the start and end positions are the same. 
Because of this, we also don't have to worry about the force that did the moving.
