We use first-principles Quantum Monte-Carlo simulations to study the Ruderman-Kittel-Kasuya-Yosida (RKKY) interaction between hydrogen adatoms attached to a graphene sheet. We find that the pairwise RKKY interactions at distances of a few lattice spacings are strongly affected by inter-electron interactions, in particular, the potential barrier between widely separated adatoms and the dimer configuration becomes wider and thus harder to penetrate. We also point out that anti-ferrromagnetic and charge density wave orderings have very different effects on the RKKY interaction. Finally, we analyze the stability of several regular adatom superlattices with respect to small displacements of a single adatom, distinguishing the cases of adatoms which populate either both or only one sublattice of the graphene lattice.