Eley-Rideal formation of hydrogen molecules on graphite, as well as competing collision induced processes, are investigated quantum dynamically at typical interstellar cloud conditions, focusing in particular on gasphase temperatures below 100 K, where Much of the chemistry of the so-called diffuse Clouds takes place on the Surface of bare carbonaceous dust grains. Collisions of gas-phase hydrogen atoms with both chemisorbed and physisorbed species are considered using available potential energy surfaces (Sha et al., J. Chem. Phys.2002 116, 7158), and state-to-state, energy-resolved cross sections are computed for a number of initial vibrational states of the hydrogen atoms bound to the Surface. Results show that (i) product molecules are internally hot in both cases, with vibrational distributions sharply peaked around few (one or two) vibrational levels, and (ii) cross sections for chemisorbed species are 2-3x smaller than those for physisorbed ones. In particular, we find that H-2 formation cross sections Out of chemically bound species decrease steadily when the temperature drops below similar to 1000 K, and this is likely due to a quantum reflection phenomenon. This Suggests that such Eley-Rideal reaction is all but efficient in the relevant gas-phase temperature range, even when gas-phase H atoms happen to chemisorb barrierless to the surface as observed, e.g., for forming so-called para dimers. Comparison with results from classical trajectory calculations highlights the need of a quantum description of the dynamics in the astrophysically relevant energy range, whereas preliminary results of an extensive first-principles investigation of the reaction energetics reveal the importance of the adopted substrate model.