We study the effects of very strong magnetic fields on the equation of state (EOS) in multicomponent, interacting matter by developing a covariant description for the inclusion of the anomalous magnetic moments of nucleons. For the description of neutron star matter, we employ a field-theoretical approach which permits the study of several models which differ in their behavior at high density. Effects of Landau quantization in ultra-strong magnetic fields ($B>10^{14}$ Gauss) lead to a reduction in the electron chemical potential and a substantial increase in the proton fraction. We find the generic result for $B>10^{18}$ Gauss that the softening of the EOS caused by Landau quantization is overwhelmed by stiffening due to the incorporation of the anomalous magnetic moments of the nucleons. In addition, the neutrons become completely spin polarized. The inclusion of ultra-strong magnetic fields leads to a dramatic increase in the proton fraction, with consequences for the direct Urca process and neutron star cooling. The magnetization of the matter never appears to become very large, as the value of $|H/B|$ never deviates from unity by more than a few percent. Our findings have implications for the structure of neutron stars in the presence of large frozen-in magnetic fields.