Let's revisit the calculation of the capacitance of parallel plates. The capacitance is defined as \(C={Q\over\Dl V}\), and we found the potential difference between the plates by integrating the electric field. So $$C=\frac{Q}{\int E_z\,dz}$$ Notice that the capacitance is inversely proportional to the electric field between the plates. If I can make that field smaller, then the capacitance would be bigger.
Now remember what happens when you place an insulator in an electric field? The insulator polarizes, creating a counterfield which partially cancels out the original field, so that the net electric field inside the insulator is smaller than the field outside, by a factor of the dielectric constant \(\kappa\).
Consider, however, that the materials with the highest dielectric constants are the metals: a pure conductor has \(\kappa=\infty\). Of course, we can't insert metal in between the plates of a capacitor: it would immediately discharge. Even if you use an insulator, you must look out for the phenomenon of electric breakdown mentioned in . If you place too much charge on a capacitor, so that the electric field between the plates exceeds the breakdown threshold of the insulator between them (and air counts as an insulator in this case!), then the insulator will become a temporary conductor, and the capacitor will discharge.
To construct a high-capacitance capacitor, then, we would like to find materials which have high dielectric constants and high breakdown thresholds. There are other tricks one can use to construct these ultracapacitors, including creating battery-capacitor hybrids which have the benefits of both.