In this paper, we analyze the effect of electrode surface roughness on the capacitance of Ionic Polymer Metal Composites (IPMCs). We use the linearized Poisson-Nernst-Planck (PNP) model to describe the steady-state spatial distribution of the electric potential and counterion concentration in the polymer region. We account for the electrode surface roughness by solving the PNP model in a three-dimensional region, whose planar dimensions are infinite and whose transverse dimension is varying in the neighborhood of a nominal constant thickness. In this framework, the electrode roughness is described by a zero-mean function whose key-features, such as spatial correlation and peak-to-peak variation, can be potentially inferred by IPMC microscopy. We use the method of asymptotic expansions to determine a second-order accurate solution of the PNP model in terms of the statistical properties of the electrode surface. Further, we establish a handleable closed-form expression for the IPMC capacitance that elucidates the interplay among the IPMC nominal dimensions, the statistical properties of the electrode surface, and the Debye screening length. We specialize our findings to isotropic surface roughness models, including random and fractal roughness. We validate our theoretical findings through extensive experimental work on Nafion-based IPMCs.