A review of surface structures of bare and adsorbate-covered GaN (0001) and (000) surfaces is presented, including results for In, Mg, Si, and H adsorbates. Emphasis is given to direct determination of surface structure employing experimental techniques such as scanning tunneling microscopy, electron diffraction, and Auger electron spectroscopy, and utilizing first principles computations of the total energy of various structural models. Different surface stoichiometries are studied experimentally by varying the surface preparation conditions (e.g. Ga-rich compared to N-rich), and the stoichiometry is included in the theory by performing calculations for various chemical potentials of the constituent atoms. Based on the work reviewed here, surface reconstructions for plasma-assisted molecular beam epitaxy growth of GaN (0001) and (000) surfaces are fairly well understood, but reconstructions for reactive molecular beam epitaxy or for metal-organic vapor phase epitaxy (both involving H, at moderate and high temperatures, respectively) are less well understood at present.