How does a capacitor store energy?

Simply, a capacitor stores energy in the electric field. This, however, is not a satisfying statement.
To get to the nitty gritty of this question we need to consider just how a capacitor works.
A capacitor can hold charge. This is why the name is similar to capacity, it stores things.
As a capacitor is charged (by someone applying voltage across it), electricity builds up on the plates inside the capacitor. Positive charge builds up on one side and negative charge on the other. Because these plates are separated by a fixed distance (they are pretty strongly fixed and therefore for all intents and purposes don’t move).
This separation of charge across some distance sets up a potential difference (voltage). That means if we stop applying voltage the charge wants to equalize, and the capacitor will “leak” current to restore even charge on either plates.
Thus, the energy is stored by creating a difference in charge.

The capacitor essential made from two metal plates separated by a distance with a material called the dielectric in the between which typically is an insulator material – it does not conduct electricity.
When charged (by a battery for example) it stores a charge the plates (electrons). This creates an electric field between the plates of the capacitor. The electric field has an energy associate with it.
The situation with the charge on the capacitor is like a ball held at a certain height, h, above the ground in gravity. It has potential energy equal to mgh in the gravity field. When you release the ball it drops and the potential energy is converted into kinetic energy.
For the capacitor, the electric charge the plate sets up an electric field between the two plates. The electric field holds potential energy. When a load (resistor or a motor) is attached to the plates of the capacitor, it discharges the charge and converts the potential energy stored in the electric field, into electric energy that drives electrons through the resistor or motor. If is is a motor it does work on the motor which is converted into mechanical energy. If it is a resistor, it heats up the resistor.