Magnesium and its alloys have shown a great potential in effective hydrogen storage due to their advantages of high volumetric/gravimetric hydrogen storage capacity and low cost. However, the use of these materials in fuel cells for automotive applications at the present time is limited by high hydrogenation temperature and sluggish sorption kinetics. This paper presents the recent results of design and development of magnesium-based nanocomposites demonstrating the catalytic effects of carbon nanotubes and transition metals on hydrogen adsorption in these materials. The results are promising for the application of magnesium materials for hydrogen storage, with significantly reduced absorption temperatures and enhanced ab/desorption kinetics. High level Density Functional Theory calculations support the analysis of the hydrogenation mechanisms by revealing the detailed atomic and molecular interactions that underpin the catalytic roles of incorporated carbon and titanium, providing clear guidance for further design and development of such materials with better hydrogen storage properties.