It's better to think of a capacitor as an energy storage device than as a charge storage device. When current flows into a capacitor, a voltage accumulates at the terminals. This voltage is separated by the distance between the plates and thus creates an electric field. This field is where the energy is stored. Inductors, on the other hand, store energy with magnetic fields.
As the current flows, opposite charges accumulate on each opposite plate of the capacitor. The electrons are trying to go around the circuit, but they get stopped at the plate of the capacitor, leaving a negative charge on one side and a positive charge on the other. The magnitude of each charge can be described by the equation:
C = Q/V
The current will keep flowing and charge will keep accumulating until the circuit with the capacitor is stable. For example, if the circuit was simply a battery, a resistor, and a capacitor in series, current would continue to flow until the capacitor voltage was equal to the battery voltage. Thus, in a steady-state DC circuit, where no currents are changing, a capacitor appears as an open circuit with the accumulated charge proportional to the voltage across the terminals and the capacitance.
However, for any circuit that is not DC, a better way to describe the behavior of capacitors is:
I = C*(dV/dt)
Therefore, if you have a sine wave voltage source, the current flowing "through" the capacitor is constantly changing and the accumulated charge is never steady. Imagine tipping a half full water bottle back and forth. The water is not flowing continuously like current in a DC circuit, but it is still doing work. If you had some bizarre turbine device in the water bottle, it would be constantly spinning, stopping only to change direction when the bottle is tipped the other way.
Finally, in a DC circuit, equal and opposite charges are stored on each side plate of the capacitor. The capacitor does not store electrons at all. It stores a charge. Electrons from one side travel all the way around the circuit to the other side as provoked by an external voltage difference. The result is an concentration of electrons on one side and an absence on the other, a charge. In an AC circuit, this same phenomenon happens, but is consistently changing. As soon the supply voltage changes, the electrons are not attracted to the plates the same way and begin to mobilize. If these electrons happen to pass through a load, like a lightbulb, on the way, they will do work and the lightbulb will turn on. Thus, the current is not actually flowing around the circuit. It is simply sloshing back and forth like water in a bottle. However, all it takes to light the bulb is moving electrons. The bulb doesn't care which way they are moving, and your eyes can't perceive the change in direction so long as the switching speed is fast enough.
I would also like to note that we are talking about ideal capacitors. In practice, at high enough frequencies, capacitors will look like inductors (V = L*(di/dt)).
To answer the specific question: Where is the charge stored in a capacitor?
Within in a complete capacitor, no net charge is stored. However, using the parallel plate model, equal and opposite charges of magnitude Q are located on each of the plates. When an external voltage is applied to a capacitor, the electrons flee from the plate with a higher potential and are attracted to the plate with a lower potential. These accumulated electrons form a negative charge on that plate and the absence of electrons from the other plate form a positive charge. The actual magnitude of each, total charge Q is determined by the voltage V and the capacitance C.