Mind you, you might instead keep the voltage constant (rather than the charges), perhaps by keeping both plates plugged in to a battery the whole time. In that case, the story changes:
* Voltage is (morally) equal to electric field times distance, so here if the separation between the plates doubles then the electric field must be cut in half.
* The plates' area is fixed, so the volume between them is proportional to their separation.
* The same fact from before about energy density being proportional to electric field strength squared applies, and total energy is still energy density times the volume between the plates.
So combining these ideas, we can see that the total energy stored between the plates will wind up decreasing as the plates are pulled apart, because the decreasing field winds up being squared when finding the total energy.
That seems very strange! Opposite charges attract, after all, so you'd still expect that you would need to do work to pull the plates apart. The subtlety here is that the battery's stored energy is changing in this process as well. (Let's assume a rechargeable battery for the moment.) As the plates separate, the charge on each plate goes down in proportion to the reduced electric field in between, so there's suddenly a lot of excess charge that needs to go somewhere. That means that the extra positive charges will be forced back into the battery's + side and the extra negative charges will be forced back into its - side. And that process stores additional energy. I haven't done the calculation, but I assume that this increase in energy will more than compensate for the decrease of energy in the capacitor itself (in exactly the right proportion to allow for the work of pulling the plates apart).
* Voltage is (morally) equal to electric field times distance, so here if the separation between the plates doubles then the electric field must be cut in half.
* The plates' area is fixed, so the volume between them is proportional to their separation.
* The same fact from before about energy density being proportional to electric field strength squared applies, and total energy is still energy density times the volume between the plates.
So combining these ideas, we can see that the total energy stored between the plates will wind up decreasing as the plates are pulled apart, because the decreasing field winds up being squared when finding the total energy.
That seems very strange! Opposite charges attract, after all, so you'd still expect that you would need to do work to pull the plates apart. The subtlety here is that the battery's stored energy is changing in this process as well. (Let's assume a rechargeable battery for the moment.) As the plates separate, the charge on each plate goes down in proportion to the reduced electric field in between, so there's suddenly a lot of excess charge that needs to go somewhere. That means that the extra positive charges will be forced back into the battery's + side and the extra negative charges will be forced back into its - side. And that process stores additional energy. I haven't done the calculation, but I assume that this increase in energy will more than compensate for the decrease of energy in the capacitor itself (in exactly the right proportion to allow for the work of pulling the plates apart).