We investigate the rest-frame ultraviolet (UV, λ ∼ 2000 Å) surface brightness (SB) evolution of galaxies up to z ∼ 6 using a variety of deep Hubble Space Telescope (HST) imaging. UV SB is a measure of the density of emission from mostly young stars and correlates with an unknown combination of star formation rate, initial mass function, cold gas mass density, dust attenuation, and the size evolution of galaxies. In addition to physical effects, the SB is, unlike magnitude, a more direct way in which a galaxy's detectability is determined. We find a very strong evolution in the intrinsic SB distribution that declines as (1+ z)3, decreasing by 4-5 mag arcsec-2 between z = 6 and z = 1. This change is much larger than expected in terms of the evolution in UV luminosity, sizes, or dust extinction, and we demonstrate that this evolution is "unnatural"and due to selection biases. We also find no strong correlation between mass and UV SB. Thus, deep HST imaging is unable to discover all of the most massive galaxies in the distant universe. Through simulations we show that only ∼15% of galaxies that we can detect at z = 2 would be detected at high z. We furthermore explore possible origins of high-SB galaxies at high z by investigating the relationship between intrinsic SB and star formation rates. We conclude that ultra-high-SB galaxies are produced by very gas-rich dense galaxies that are in a unique phase of evolution, possibly produced by mergers. Analogs of such galaxies do not exist in the relatively nearby universe.