Water associates with small hydrophobic gas particles to form stable solid structures, called clathrate hydrates, under certain conditions of pressure and temperature. Addition of guest molecules can alter both the conditions for clathrate stability as well as the occupation of trapped gas particles. While methane gas molecules induce formation of the best known clathrate hydrates, new experiments show that even small hydrogen molecules can support stable clathrate structures, leading to the possibility of a new hydrogen storage material. We report on ab initio studies of clustering reactions between water and small hydrophobic gas particles to elucidate the fundamental mechanism of clathrate hydrate formation and conditions that lead to increased gas occupation.