Galaxies with stellar masses near M* contain the majority of stellar mass in the universe, and are therefore of special interest in the study of galaxy evolution. The Milky Way (MW) and Andromeda (M31) have present day stellar masses near M*, at 5x10^10 Msol (MW-mass) and 10^11 Msol (M31-mass). We study the typical progenitors of these galaxies using ZFOURGE, a deep medium-band near-IR imaging survey, which is sensitive to the progenitors of these galaxies out to z~3. We use abundance-matching techniques to identify the main progenitors of these galaxies at higher redshifts. We measure the evolution in the stellar mass, rest-frame colors, morphologies, far-IR luminosities, and star-formation rates combining our deep multiwavelength imaging with near-IR HST imaging from CANDELS, and far-IR imaging from GOODS-H and CANDELS-H. The typical MW-mass and M31-mass progenitors passed through the same evolution stages, evolving from blue, star-forming disk galaxies at the earliest stages, to redder dust-obscured IR-luminous galaxies in intermediate stages, and to red, more quiescent galaxies at their latest stages. The progenitors of the MW-mass galaxies reached each evolutionary stage at later times (lower redshifts) and with stellar masses that are a factor of 2-3 lower than the progenitors of the M31-mass galaxies. The process driving this evolution, including the suppression of star-formation in present-day M* galaxies requires an evolving stellar-mass/halo-mass ratio and/or evolving halo-mass threshold for quiescent galaxies. The effective size and star-formation rates imply that the baryonic cold-gas fractions drop as galaxies evolve from high redshift to z~0 and are strongly anticorrelated with an increase in the S\'ersic index. Therefore, the growth of galaxy bulges in M* galaxies corresponds to a rapid decline in the galaxy gas fractions and/or a decrease in the star-formation efficiency.