If I know the total charge in a battery, let's say 5000 Ah, and I want to find how much energy is stored in the battery, I multiply the total charge by the voltage E = Q·V; for example, for 12 V I will get 12·5000.
Now if I know the charge in a capacitor, and I want to find the energy stored, E = ½·C·V2 where Q = C·V, so I get E = ½·Q·V.
Why is there a difference?
Short answer:
an ideal battery has constant voltage \$U_{nom}\$ (nominal voltage) until it's empty, so energy stored is: \begin{aligned} E &= U_{nom} \times I \times T\\ &= U_{nom} \times \text{capacity} \end{aligned}
an ideal capacitor has voltage proportional to charge, so it decreases linearly to 0:
\begin{aligned} E &= \int_0^T U(t)I\ dt\\ &= U_{average} \times I \times T\\ &= \frac{U_0}{2} \times I \times T\\ &= U_0 \times \text{capacity} \end{aligned}
Visually, if you draw power vs time (at constant current), then you get a rectangle for a battery, and a triangle (so half the area) for a capacitor.
Long answer: If you look more into detail, specially for the battery, the energy is not exactly \$E=Q \times U\$:
For the capacitors, it's harder to say something general, but depending of the type, there can be also some rather big deviations. For example some MLCC (multi-layer ceramic capacitors) can lose 80% of their capacitance at higher voltages, and regain it at lower voltage: so you store far less energy than expected in the higher voltage part.
What the other answers are missing is the formula for the stored energy common to both cases: it is
\$E = \int_0^Q U(q)\,\mathrm{d}q\$
That is, each bit of charge accounts for energy at the individual voltage it is taken out or in. Battery chemistry maintains comparatively constant voltage, capacitor operating principle maintains voltage approximately proportional to charge. That is, unless a dielectric saturates, in which case comparatively little additional charge can cause a disproportional voltage change and thus does not add a lot of energy.
The difference is that a perfect battery is a constant voltage source. If you discharge the battery the voltage will not change until it will suddenly drop to zero when it is completely discharged.
A capacitor, even an ideal one is not. If you discharge a capacitor, the voltage will drop along the way to zero when all energy is extracted.
To get the energy stored, you have to integrate I*V over time, if you do that for an ideal battery the voltage is constant and can be pulled out of the integral and thus you have just I integrated over time which is Q.
For the capacitor V is also time dependent. So it's a bit more complex.
Now in real life a battery is of course not ideal. The end of charge voltage of a battery might be 4.2 V but most of the discharge curve will be at 3.7 or 3.6 V. Your "12 V" battery is likely to go up to 14.4 V if fully charged.
Important difference:
The voltage of capacitor rises when current is pushed into it and voltage drops when current is drawn from it. So the voltage is not constant as it is proportional to the charge stored in the capacitor. Q=I×t=C×U.
Batteries can be approximated to have constant voltage when current is drawn out or pushed in. You don't draw batteries empty down to 0V, and the voltage will not linearly depend on charge left in the battery. For example lithium batteries have 3.6V printed on them. In reality it is only the nominal voltage used for calculations, and the actual battery voltage might be 4.2V when full and 3.0V when empty, and will not change linearly, but the effective voltage between full and empty can be calculated to be 3.6V. Thus moved charge is Q=I×t, but Q=C×U won't apply to batteries, only capacitors.
An even simpler way of describing the difference is to say that if a device has a voltage that changes linearly with charge from \$V_{max}\$ to \$V_{min}\$, the energy will be proportional to \$\frac{Q\cdot(Vmax+Vmin)}{2}\$. If \$V_{min}=0\$, then the energy will be \$\frac{Q\cdot(V_{max}+0)}{2}\$, i.e. \$\frac{Q\cdot V_{max}}{2}\$; if \$V_{min}=V_{max}\$, the energy will be \$\frac{Q\cdot (V_{max}+V_{max})}{2}\$, i.e. \$Q\cdot V_{max}\$. If \$V_{min}\$ is between 0 and \$V_{max}\$, then the energy will be between \$\frac{Q\cdot V_{max}}{2}\$ and \$Q\cdot V_{max}\$.
If you have a voltage source and you want to charge a capacitor, you inevitably utilize circuit resistance (either an intentional resistor or unintentional cable resistance) to ensure that the peak current during charging is not stupidly high. And, if you do the math, the total energy acquired by the capacitor is: -
$$W = \dfrac{1}{2}\cdot CV^2$$
Whereas, the total energy delivered by the voltage source is this: -
$$W = CV^2$$
So, the lost energy (50%) is due to the cable resistance or intentional resistance.
As a comparison, if your voltage source was programmable and could be set to ramp up in voltage, then the energy delivered to the capacitor would be the energy liberated from the voltage source. In other words, when trying to charge capacitors from a hard voltage source, you get a collision situation. This doesn't happen with inductors; apply a voltage across an inductor and the current rises linearly and energy is stored very efficiently. This is why we use them in switch mode power supplies.
