Because of permittivity $\varepsilon$. Capacitance is calculated as:
$$C=\varepsilon_0\varepsilon \frac Ad$$
$\varepsilon_0$ is a natural constant (vacuum permittivity). $A$ is plate area and $d$ is separation.
$A$ and $d$ depend on the conductive materials. But $\varepsilon$ depends on the in-between material - the so-called dielectric.
The dielectric may contain dipoles, asymmetrically charged molecules, that are able to twist and rotate when an electric field is established between the capacitor plates. When all such dipoles are biased and turned the same way, then all their "negative ends" point towards the positive plate, and all their "positive ends" towards the negative plate. Each of them now attracts the charges on the plates. Their combined attraction "strength" may have a significant influence in pulling a few more charges to theplates.
The dipoles relate directly to $\varepsilon$. Water is a good example with a high value around $\varepsilon\approx 80$, because water is an oddly asymmetric molecule.
When a battery or other voltage source is applied to a capacitor, it will push charges to the plates until the accumulated repulsion force of those charges at the plates balances out the battery push. If there is a strong dielectric between the plates, then its dipoles will "help out" the battery by "pulling a few extra charges" to the plate. In this sense, the dielectric material increases the amount of charge that can be stored on those plates - the dielectric increases the capacitance.
Dielectric breakdown
Furthermore, a dielectric helps against so-called dielectric breakdown. Breakdown happens for instance during lightning storms. The voltage (potential difference between cloud and ground) is so large that charges (current) want to move across the separation so badly, that the usually insulating air can't resist them from moving. When charges in this way flow through an insulator, this is dielectric breakdown. The critical limit is called the breakdown voltage.
If you want to store some amount of charge in your capacitor, but your capacitor is not that large (has a low $C$), you will have to apply larger voltage $V$. The relationship is this:
$$Q=CV$$
$Q$ is the amount of charge that you want to store. For a smaller capacitance $C$, you must increase the voltage. Maybe this will make you reach the breakdown voltage, so it is impossible. But with a good dielectric, you can increase $C$ - in other words, you can reach the intended amount of stored charge with a lower voltage.