In theory, provided that the surface area of the electrode remains constant and that the electrode material is conductive, the capacitance will not differ significantly when using different metals. This is just a consequence of the fact that for parallel plates, the capacitance only really depends on plate surface area.
However, for modern electrochemical capacitors this relation is not quite correct; a large part of the capacitance is due to a surface effect called double-layer capacitance (image from http://en.wikipedia.org/wiki/File:EDLC-Charge-Distribution.png):
The capacitance of electrolytic capacitors and supercapacitors is thus largely dependent on the effective surface area of the electrode material used, and thus materials with large surface areas (like activated carbon or other porous materials) are often used. This allows one to construct capacitors with far higher capacitances than would otherwise be expected from a naive application of the parallel plate capacitance formula.