Aims. Because of their catalytic properties, interstellar dust grains are crucial to the formation of H2, the most abundant molecule in the Universe. The formation of molecular hydrogen strongly depends on the ability of H atoms to stick on dust grains. In this study we determine the sticking coefficient of H atoms chemisorbed on graphitic surfaces, and estimate its impact on the formation of H2. Methods. The sticking probability of H atoms chemisorbed onto graphitic surfaces is obtained using a mixed classical-quantum dynamics method. In this, the H atom is treated quantum-mechanically and the vibrational modes of the surface are treated classically. The implications of sticking for the formation of H2 are addressed by using kinetic Monte Carlo simulations that follow how atoms stick, move and associate with each other on dust surfaces of different temperature. Results. In our model, molecular hydrogen forms very efficiently for dust temperatures lower than 15 K through the involvement of physisorbed H atoms. At dust temperatures higher than 15 K and gas temperatures lower than 2000 K, H2 formation differs strongly if the H atoms coming from the gas phase have to cross a square barrier (usually considered in previous studies) or a barrier obtained by density functional theory (DFT) calculations to become chemisorbed. The product of the sticking times efficiency can be increased by many orders of magnitude when realistic barriers are considered. If graphite phonons are taken into account in the dynamics calculations, then H atoms stick better on the surface at high energies, but the overall H2 formation efficiency is only slightly affected. Our results suggest that H2 formation can proceed efficiently in photon-dominated regions, X-ray dominated regions, hot cores and in the early Universe when the first dust is available.