We have measured the laser-induced fluorescence excitation spectra of the 3 P-1(1)0<-- 3 S-1(0) transition of Mg atoms solvated in helium nanodroplets. The observed blue shifts and line broadenings mirror the shifts and broadenings observed in studies of Mg atoms solvated in bulk liquid helium. This similarity allows us to conclude that Mg atoms reside in the interior of the helium droplet. The 3 P-1(1)0<-- 3 S-1(0) transition shows a splitting which we attribute to a quadrupolelike deformation of the cavity which forms around the solute atom after excitation. Temporal evolution of the fluorescence from the solvated 3 P-1(1)0 Mg yields a longer lifetime (2.39 +/- 0.05 ns) than found in vacuum (1.99 +/- 0.08 ns). This difference can be accounted for quantitatively by evaluation of the anisotropic distribution of the helium density in the neighborhood of the excited Mg atom. The question of solvation vs surface location for the guest atoms is also discussed in light of the model of Ancilotto [F. Ancilotto, P. B. Lerner, and M. W. Cole, J. Low Temp. Phys. 101, 1123 (1995)], of existing metal atom-helium potential energy functions, and of our own calculations for the MgHe and CaHe ground states. While the Ancilotto model successfully predicts solvation (or lack of it) if the solvation parameter of the guest atom is not too near the threshold of 1.9, the present knowledge of the interatomic potentials is not precise enough to test the model in the neighborhood of the critical value.