We report a novel, reliable, and scalable technique for the surface nanostructuring of GaN by colloidal lithography. Moth-eye protuberances of varying dimensions have been formed on bulk GaN substrates and on samples containing an InGaN multiple-quantum-well active layer, grown by metal organic chemical vapor deposition. Angle-resolved optical characterization and photoluminescence (PL) indicates enhanced transmission through these samples compared to flat, unstructured surfaces. We analyze the potential mechanisms causing this enhancement, such as recycling of PL pump light, improved first-pass extraction, and improved diffuse scattering. The impact of these effects is evaluated using finite-difference time-domain and effective medium theory simulations. Light extraction with moth-eye nanostructures is compared to state-of-the-art methods for c-plane and semipolar GaN surface roughening.