We performed first-principles calculations to investigate the hydrogen storage characteristics of carbon-based 3-D solid structures, called covalently bonded graphenes (CBGs). Using the density functional method and the Moller-Plesset perturbation method, we show that H-2 molecular binding in the CBGs is stronger than that on an isolated graphene with an increase of 20 to similar to 150% in binding energy, which is very promising for storage at ambient conditions. We also suggest that the CBGs of appropriate size can effectively work as frameworks for transition metal dispersion. The adsorption properties of hydrogen on the metal atoms dispersed inside the CBGs are also presented.