Ab initio density functional theory (DFT) calculations are performed to explore possible catalytic effects on the dissociative chemisorption of hydrogen on a Mg(0001) surface when carbon is incorporated into Mg materials. The computational results imply that a C atom located initially on a Mg(0001) surface can migrate into the subsurface and occupy an fcc interstitial site, with charge transfer to the C atom from neighboring Mg atoms. The effect of subsurface C on the dissociation of H-2 on the Mg(0001) surface is found to be relatively marginal: a perfect sublayer of interstitial C is calculated to lower the barrier by 0.16 eV compared with that on a pure Mg(0001) surface. Further calculations reveal, however, that sublayer C may have a significant effect in enhancing the diffusion of atomic hydrogen into the sublayers through fcc channels. This contributes new physical understanding toward rationalizing the experimentally observed improvement in absorption kinetics of H2 when graphite or single walled carbon nanotubes (SWCNT) are introduced into the Mg powder during ball milling.