Mg-based hydrogen storage alloys have become a research hotspot in recent years owing to their high hydrogen storage capacity, good reversibility of hydrogen absorption/desorption, low cost, and abundant resources. However, its high thermodynamic stability and slow kinetics limit its application, so the modification of Mg-based hydrogen storage alloys has become the development direction of Mg-based alloys. Transition metals can be used as catalysts for the dehydrogenation of hydrogen storage alloys due to their excellent structural, electrical, and magnetic properties. Graphene, because of its unique sp2 hybrid structure, excellent chemical stability, and a specific surface area of up to 2600 m2/g, can be used as a support for transition metal catalysts. In this paper, the internal mechanism of graphene as a catalyst for the catalysis of Mg-based hydrogen storage alloys was analyzed, and the hydrogen storage properties of graphene-catalyzed Mg-based hydrogen storage alloys were reviewed. The effects of graphene-supported different catalysts (transition metal, transition metal oxides, and transition metal compounds) on the hydrogen storage properties of Mg-based hydrogen storage alloys were also reviewed. The results showed that graphene played the roles of catalysis, co-catalysis, and inhibition of grain aggregation and growth in Mg-based hydrogen storage materials.