How is the stored charge removed during reverse recovery time?
During reverse recovery, the negative voltage at the p terminal attracts holes away from the depletion zone, and the positive voltage at the n terminal attracts electrons away from the depletion zone. The remaining minority carriers drift across the depletion zone and either recombine or, now as majority carriers in a reverse biased diode, get swept to the terminals. The carriers that get swept to the terminals form reverse recovery current.
Wouldn't the battery be putting more electrons into the p side?
Very few new minority carriers are introduced into either the n or p zones, because the ohmic metal-semiconductor junction doesn't allow that to any appreciable degree. (The minority carriers in a diode are almost all present because during forward bias, majority carriers crossed the depletion zone and became minority carriers.)
huge current flows during the reverse recovery phase right? This means the battery is putting more electrons into the p side. Is my understanding ok?
The current may be large, but only for a very short time, while the existing charge is "removed". So, no, "large" current does not imply that electrons are entering the p-semiconductor from the terminal (to any appreciable extent). Thermal energy does allow some electrons to enter the p side from the terminal. If the diode is at room temperature, there will not be many. If the diode is hot, a great deal more will flow. But strictly speaking, that is not reverse recovery current, but reverse leakage current.
Addendum: The original question was about how stored charge was removed during reverse recovery. However, discussion in the comments has revealed also an interest in how the charge that exists on both sides of a reverse biased junction (or even an unbiased junction) comes about. This discussion reveals some misconceptions that I would like to address.
The misconception is around the notion that electrons may leave a negatively charged wire connected to the p region, enter the p region, cross over the junction to the n region, and then enter the positively charged wire.
Mostly that does not happen. When electrons enter the p-region from a wire, it is almost always to recombine with holes in the p-region. It is possible for electrons to enter the p region from the wire and become minority carriers, but that is rare. (It increases with temperature, but it is rare). Almost all of the minority carriers in a diode begin their career as majority carriers in the oppositely doped region, and cross the junction. More about that in a minute.
Another answer states:
As holes flow into the n-side from the positive terminal of the battery, some of them are lost to recombination. These can be replaced by the stored minority carrier holes on the n-side.
This is the same mistake. Holes very rarely flow from a wire into the n-region.
However, when an pn junction is unbiased (or reverse biased) there are holes in the n region near the junction, and electrons in the p region near the junction. How does this state of affairs come to be?
The answer is diffusion current. We are all familiar with drift current, which is the flow of carriers due to an electric field. But all carriers have thermal energy associated with them, and there is a random motion caused by this thermal energy. If there is an region which in which the concentration of one species of carrier is higher than in a neighboring region, then those carriers will tend to diffuse from the region of higher concentration to the region of lower concentration. This is called diffusion current. Diffusion current can occur even against a voltage gradient. This in fact happens at a pn junction. Electrons, which are plentiful in the n region diffuse across the junction to the p region. Holes, which are plentiful in the p region diffuse across the junction to the n region. This sets up a negative charge on the p side and a positive charge on the n side. These charges in turn create an electric field. The electric field causes charges to flow in the opposite direction to the diffusion current. This flow, under the influence of an electric field is a drift current. When the drift current and the diffusion current are equal and opposite, a dynamic equilibrium is established. It is important to note that the equilibrium point does not occur when the electric field is zero, but when there exists a significant and important non-zero electric field.
It is also important to understand that the field is not created by currents from outside the diode, but from currents internal to the diode. Currents that basically only exist near the junction. No external current is required to create this separation of charges. In a reverse biased diode, almost all the free electrons in the p region came from the n region, and not from the negatively charged wire connected to the p region. Similarly, the holes in the n region came from the p region, and not from the positively charged wire connected to the n region.
This applies both to minority carriers that are left over from forward conduction, and also to the minority carriers that flank both sides of the junction when it is blocking current.