The structure and electronic properties of oxidized (0001) surfaces of GaN grown by plasma-assisted molecular beam epitaxy are investigated by scanning tunneling microscopy/spectroscopy, Auger electron spectroscopy, and first-principles theory. For oxygen exposure at room temperature an amorphous gallium oxide layer is found to form, resulting in a distribution of midgap electronic states extending out from the GaN valence band edge. The influence of these states on the electron concentration in buried AlGaN/GaN heterojunctions is discussed.