The energy is stored in the electric field between the two "plates" this electric field spans the dielectric material. When charge gets onto the plates, the dielectric polarizes at the molecular level. "Work" is performed to do this. When the capacitor discharges, work is performed to get the charge to flow. And so when the cap is charged, there is a sort of "potential energy" stored in the electric field. It takes energy to build the E-field and it takes energy to collapse it.