Using deep NIR VLT/ISAAC and optical HST/WFPC2 imaging in the fields of the HDFS and MS1054-03, we study the rest-frame UV-to-optical colors and magnitudes of galaxies to z~3. While there is no evidence for a red sequence at z~3, there does appear to be a well-defined color-magnitude relation (CMR) for blue galaxies at all redshifts, with more luminous galaxies having redder U-V colors. The slope of the blue CMR is independent of redshift d(U-V)/dMV = -0.09 (0.01) and can be explained by a correlation of dust-reddening with luminosity. The average color at fixed luminosity reddens strongly Delta(U-V) = 0.75 from z~3 to z=0, much of which can be attributed to aging of the stars. The color scatter of the blue sequence is relatively small sigma(U-V) = 0.25 (0.03) and constant to z~3, but notably asymmetrical with a sharp blue ridge and a wing towards redder colors. We explore sets of star formation histories to study the constraints placed by the shape of the scatter at z=2-3. One particular set of models, episodic star formation, reproduces the detailed properties very well. For a two-state model with high and low star formation, the duty cycle is constrained to be > 40% and the contrast between the states must be a factor > 5 (or a scatter in log(SFR) of > 0.35 dex around the mean). However, episodic models do not explain the observed tail of very red galaxies, primarily Distant Red Galaxies (DRGs), which may have ceased star formation altogether or are more heavily obscured. Finally, the relative number density of red, luminous MV < -20.5 galaxies increases by a factor of ~ 6 from z = 2.7 to z = 0.5, as does their contribution to the total rest-frame V-band luminosity density. We are likely viewing the progressive formation of red, passively evolving galaxies.