Hydrogen-based economy has a great potential for addressing the world's environmental concerns by using hydrogen as its future energy carrier. Hydrogen can be stored in gaseous, liquid and solid-state form, but among all solid-state hydrogen storage materials (metal hydrides) have the highest energy density. However, hydrogen accessibility is a challenging step in metal hydride-based materials. To improve the hydrogen storage kinetics, effects of functionalized catalysts/dopants on metal atoms have been extensively studied. The nanostructuring of metal hydrides is a new focus and has enhanced hydrogen storage properties by allowing higher surface area and thus reversibility, hydrogen storage density, faster and tunable kinetics, lower absorption and desorption temperatures, and durability. The effect of incorporating nanoparticles of carbon-based materials (graphene, C60, carbon nanotubes (CNTs), carbon black, and carbon aerogel) showed improved hydrogen storage characteristics of metal hydrides. In this critical review, the effects of various carbon-based materials, catalysts, and dopants are summarized in terms of hydrogen-storage capacity and kinetics. This review also highlights the effects of carbon nanomaterials on metal hydrides along with advanced synthesis routes, and analysis techniques to explore the effects of encapsulated metal hydrides and carbon particles. In addition, effects of carbon composites in polymeric composites for improved hydrogen storage properties in solid-state forms, and new characterization techniques are also discussed. As is known, the nanomaterials have extremely higher surface area (100-1000 time more surface area in m2/g) when compared to the bulk scale materials; thus, hydrogen absorption and desorption can be tuned in nanoscale structures for various industrial applications. The nanoscale tailoring of metal hydrides with carbon materials is a promising strategy for the next generation of solid-state hydrogen storage systems for different industries.