We used the continuous-time random-walkMonte Carlo technique to study anew the formation of H-2 on the surfaces of interstellar dust grains in diffuse interstellar clouds. For our study, we considered three different grain materials, olivine (a polycrystalline silicate), amorphous silicate, and amorphous carbon, as well as a grain temperature that depends on granular size. For some runs, we included temperature fluctuations. Four different granular surfaces were used, one "flat" with one type of binding site due to physisorption, one "rough" with five different types of physisorption binding sites due to lateral forces, and two with sites for chemisorption, one in which chemisorption sites are entered through precursor physisorption sites, and one in which chemisorption is direct but occurs with a barrier for the adsorption of the first hydrogen atom. We found that on flat and rough olivine surfaces, molecular hydrogen is formed at low efficiencies, with smaller grains contributing very little despite their large numbers due to high temperatures. For flat amorphous carbon and amorphous silicate surfaces, the efficiency increases, reaching unity for the largest grains. For models with barrierless chemisorption, the efficiency of formation of H-2 is near unity at all grain sizes considered, while for direct chemisorption via a barrier, we found efficiencies of 0.13-0.6 depending upon the barrier, but independent of grain size. Treating the flat olivine and amorphous silicate surfaces with temperature fluctuations increases the efficiency of H-2 formation.