We report an investigation on the adsorption of small gas molecules (O(2), CO, NO(2) and NH(3)) on pristine and various transition metal embedded graphene samples using a first-principles approach based on density-functional theory (DFT). The most stable adsorption geometry, energy, charge transfer, and magnetic moment of these molecules on graphene embedded with different transition metal elements are thoroughly discussed. Our calculations found that embedded transition metal elements in general can significantly enhance the interactions between gas molecules and graphene, and for applications of graphene-based catalysis, Ti and Au may be the best choices among all transition metal elements. We also expect a detailed analysis of the electronic structures and magnetic properties of these systems to shed light on future applications of graphene-based gas sensing and spintronics.