We present a density-functional-theory study of transition-metal atoms (Sc-Zn, Pt, and Au) embedded in single and double vacancies (SV and DV) in a graphene sheet. We show that for most metals, the bonding is strong and the metal-vacancy complexes exhibit interesting magnetic behavior. In particular, an Fe atom on a SV is not magnetic, while the Fe@DV complex has a high magnetic moment. Surprisingly, Au and Cu atoms at SV are magnetic. Both bond strengths and magnetic moments can be understood within a simple local-orbital picture, involving carbon sp(2) hybrids and the metal spd orbitals. We further calculate the barriers for impurity-atom migration, and they agree well with available experimental data. We discuss the experimental realization of such systems in the context of spintronics and nanocatalysis.