We investigate the average physical properties and star formation histories (SFHs) of the most UV-luminous star-forming galaxies at z similar to 3.7. Our results are based on the average spectral energy distributions (SEDs), constructed from stacked optical-to-infrared photometry, of a sample of the 1913 most UV-luminous star-forming galaxies found in 5.3 deg(2) of the NOAO Deep Wide-Field Survey. We find that the shape of the average SED in the rest optical and infrared is fairly constant with UV luminosity, i.e., more UV-luminous galaxies are, on average, also more luminous at longer wavelengths. In the rest UV, however, the spectral slope beta (equivalent to dlogF(lambda)/dlog lambda; measured at 0.13 mu m <lambda(rest) <0.28 mu m) rises steeply with the median UV luminosity from -1.8 at L approximate to L* to -1.2 (L approximate to 4-5L*). We use population synthesis analyses to derive their average physical properties and find that (1) L(UV) and thus star formation rates (SFRs) scale closely with stellar mass such that more UV-luminous galaxies are also more massive, (2) the median ages indicate that the stellar populations are relatively young (200-400 Myr) and show little correlation with UV luminosity, and (3) more UV-luminous galaxies are dustier than their less-luminous counterparts, such that L approximate to 4-5L* galaxies are extincted up to A(1600) = 2 mag while L approximate to L* galaxies have A(1600) = 0.7-1.5 mag. We argue that the average SFHs of UV-luminous galaxies are better described by models in which SFR increases with time in order to simultaneously reproduce the tight correlation between the UV-derived SFR and stellar mass and their universally young ages. We demonstrate the potential of measurements of the SFR-M(*) relation at multiple redshifts to discriminate between simple models of SFHs. Finally, we discuss the fate of these UV-brightest galaxies in the next 1-2 Gyr and their possible connection to the most massive galaxies at z similar to 2.