Using molecular dynamics simulations with recently developed importance sampling methods, we show that the differential capacitance of a model ionic liquid based double-layer capacitor exhibits an anomalous dependence on the applied electrical potential. Such behavior is qualitatively incompatible with standard mean-field theories of the electrical double layer, but is consistent with observations made in experiment. The anomalous response results from structural changes induced in the interfacial region of the ionic liquid as it develops a charge density to screen the charge induced on the electrode surface. These structural changes are strongly influenced by the out-of-plane layering of the electrolyte and are multifaceted, including an abrupt local ordering of the ions adsorbed in the plane of the electrode surface, reorientation of molecular ions, and the spontaneous exchange of ions between different layers of the electrolyte close to the electrode surface. The local ordering exhibits signatures of a first-order phase transition, which would indicate a singular charge-density transition in a macroscopic limit.