We study the nature of faint, red-selected galaxies at z ~ 2-3 using the Hubble Ultra Deep Field (HUDF) and Spitzer IRAC photometry. We detect candidate galaxies to H < 26 mag, probing lower-luminosity (lower mass) galaxies at these redshifts. We identify 32 galaxies satisfying the (J - H) > 1.0 mag color selection, 16 of which have unblended [3.6um] and [4.5um] IRAC photometry. We derive photometric redshifts, masses, and stellar population parameters for these objects. We find that the selected objects span a diverse range of properties over a large range of redshifts, 1 < z < 3.5. A substantial fraction (11/32) appear to be lower-redshift (z < 2.5), heavily obscured dusty galaxies or edge-on spiral galaxies, while others (12/32) appear to be galaxies at 2 < z < 3.5 whose light at rest-frame optical wavelengths is dominated by evolved stellar populations. Interestingly, by including Spitzer data many candidates for galaxies dominated by evolved stellar populations are rejected, and for only a subset of the sample (6/16) do the data favor this interpretation. We place an upper limit on the space and stellar mass density of candidate massive evolved galaxies. The z > 2.5 objects that are dominated by evolved stellar populations have a space density at most one-third that of z ~ 0 red, early-type galaxies. Therefore, at least two-thirds of present-day early-type galaxies assemble or evolve into their current configuration at redshifts below 2.5. We find a dearth of candidates for low-mass galaxies at 1.5 < z < 3 that are dominated by passively evolving stellar populations even though the data should be sensitive to them; thus, at these redshifts, galaxies whose light is dominated by evolved stellar populations are restricted to only those galaxies that have assembled high stellar mass.[Abridged] Comment: 18 pages, 10 figures, and 4 tables. Accepted for publication in ApJ