Theories that extend the Standard Model of particle physics often introduce new interactions that violate charge-parity (CP) symmetry. CP-violating effects within an atomic nucleus can be probed by measuring its nuclear magnetic quadrupole moment (MQM). The sensitivity of such a measurement is enhanced when using a heavy polar molecule containing a nucleus with quadrupole deformation. We determine how the energy levels of a molecule are shifted by the MQM and how those shifts can be measured. The measurement scheme requires molecules in a superposition of magnetic sub-levels that differ by many units of angular momentum. We develop a generic scheme for preparing these states. Finally, we consider the sensitivity that can be reached, showing that this method can reduce the current uncertainties on several CP-violating parameters.