The spillover phenomenon, which essentially involves transfer of H from a metal catalyst to a graphitic receptor, has been considered promising for efficient hydrogen storage. An open question about the spillover mechanism is how a H atom binds to graphene instead of forming the thermodynamically preferred H(2). Using ab initio calculations, we show that the catalyst saturation provides a way to the adsorption of hydrogen on the receptor by increasing the H chemical potential to a spillover favorable range. Although it is energetically unfavorable for the spillover to occur on a pristine graphene surface, presence of a phase of hydrogenated graphene facilitates the spillover by significantly improving the C-H binding. We show that thermodynamic spillover can occur, both from the free-standing and from the receptor-supported clusters. Further, the computed energy barrier of the motion of a H from the catalyst to the hydrogenated graphene is small (0.7 eV) and can be overcome at operational temperatures.