The electrode is commonly Al; it has a thin oxide layer that acts as the dielectric. The thickness of the oxide layer determines the voltage rating and also the capacitance.
Unfortunately the native oxide layer is rather porous and that makes a lousy capacitor. We use electrolytes (soap like; contains borates, phosphates etc) that block the pores and improves the performance. However, under reverse voltage, the pores get deprotected and the capacitor fails. But the electrolyte is NOT the dielectric. It becomes an extension of the other foil. Ta also has a similar oxide layer (that makes soldering Al very difficult if not impossible).