Reconstructions of the gallium nitride (0001) Ga-face and N-face surfaces have been studied using scanning tunneling microscopy, with growth performed by molecular beam epitaxy. Distinct families of reconstruction are observed on each face, with most of the structures involving the presence of one of more adlayers of gallium bonded to underlying nitrogen atoms. For the N-face, this Ga-adlayer is in a 1x1 arrangement and further reconstructions are formed by additional Ga adatoms weakly bonded on the Ga-adlayer. For the Ga-face, the Ga-adlayer is incommensurate with the GaN lattice. For both the Ga- and N-face, growth under Ga-rich conditions yields smooth surfaces whereas growth under N-rich conditions produces rough surfaces. The latter case is indicative of limited surface diffusion rates. However, in the presence of surfactant layers such as Mg or As, smooth growth is also obtained in the N-rich regime. For sufficiently high surface coverage of Mg, a remarkable transition is observed in which Ga-polar material converts to N-polarity, with the inversion domain boundary extending along the c-plane. For growth of InGaN alloys, the role of surface metal layers (mainly indium) is also found to play an important role in the growth kinetics and incorporation efficiency. @FootnoteText@ Work supported by Office of Naval Research and National Science Foundation, and performed in collaboration with V. Ramachandran, H. Chen, A. Smith, D. Greve, J. Northrup, J. Neugebauer, W. Sarney, and L. Salamanca-Riba.