We report on a formulation and implementation of a scheme to compute NMR shieldings at second-order Moller-Plesset (MP2) perturbation theory using gauge-including atomic orbitals (GIAOs) to ensure gauge-origin independence and Cholesky decomposition (CD) to handle unperturbed as well as perturbed two-electron integrals. We investigate the accuracy of the CD for the derivatives of the two-electron integrals with respect to an external magnetic field as well as for the computed NMR shieldings, before we illustrate the applicability of our CD based GIAO-MP2 scheme in calculations involving up to about one hundred atoms and more than one thousand basis functions.