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 5 × 1010 M ⊙ (defined here to be MW-mass) and 1011 M ⊙ (defined to be M31-mass). We study the typical progenitors of these galaxies using the FOURSTAR Galaxy Evolution Survey (ZFOURGE). ZFOURGE is 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 Hubble Space Telescope imaging from Cosmic Near-IR Deep Extragalactic Legacy Survey (CANDELS), and Spitzer and Herschel far-IR imaging from Great Observatories Origins Deep Survey-Herschel and CANDELS-Herschel. 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 two to three 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 SFRs 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érsic 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.