I understand that underexpanded nozzles lose efficiency, due to untapped potential in the gas before exiting the nozzle, but what happens to overexpanded nozzles? I understand that the pressure of the gas is below the pressure of the ambient atmosphere, but what does this do to the overall engine performance?
According to this article, in an overexpanded nozzle, the loss of efficiency is caused by the "pinching" of the exhaust plume by the ambient air pressure.
In grossly overexpanded nozzles, there's another, more serious problem, where the exhaust flow separates from one side of the nozzle, adhering to the opposite side, which causes very uneven heating and wear on the nozzle, and directs the thrust off the central axis of the engine.
Ignoring the complicated separation issue, there is a simple relation to calculate the effect on thrust based on mismatch of the exit plane pressure and ambient pressure, namely:
$$F = q V_e + (P_e-P_a) A_e$$
Where $P_e$ is the exit plane pressure, $P_a$ is ambient pressure, and $A_e$ is the exit plane area. $qV_e$ without the correction term gives the thrust when the exit plane pressure matches ambient. Here $q$ is mass flow and $V_e$ is exit velocity.
Taken from Robert A. Braeunig's page on Rocket Propulsion.
As Russell Borogove mentions in his answer, real world effects make the thrust degradation worse (and can even physically damage the nozzle).