We report on an investigation of the mechanisms giving rise to surface reconstruction for GaN grown by molecular beam epitaxy (MBE) on a range of different substrates. We have studied the effects of surface contamination by oxygen or arsenic and demonstrate that both can influence the surface reconstruction. We show that surface reconstruction measured by reflection high-energy electron diffraction (RHEED) is associated with excess Ga on the surface, which undergoes an order-disorder transition at about 400-500 o C. For MBE, growth on hydride vapour phase epitaxy (HVPE) GaN/SiC composite substrates having the Ga polarity the 2x2 reconstruction is intrinsic. This intrinsic reconstruction can be destroyed by heating to a high temperature or by oxidation. The intrinsic 2x2 reconstruction can also be destroyed by adding an additional monolayer of more weakly bound Ga, which can be removed by desorption at high temperature. For growth by MBE on sapphire with nitridation, a 3x3 reconstruction is observed on cooling the sample to <400 o C, but the reconstruction can be changed to 4x4 by contamination with oxygen. For growth of GaN with a N polarity by MBE on GaAs(111)B, a 4x4 reconstruction is observed on cooling to <400 o C, which may be caused by arsenic.