We report the discovery of a substantial population of star-forming galaxies at 3.0 less than or similar to z less than or similar to 3.5. These galaxies have been selected using color criteria sensitive to the presence of a Lyman continuum break superposed on an otherwise very blue far-UV continuum, and then confirmed with deep spectroscopy on the W. M. Keck telescope. The surface density of galaxies brighter than R = 25 with 3.0 less than or similar to z less than or similar to 3.5 is 0.4 +/- 0.07 galaxies arcmin(-2) approximately 1.3% of the deep counts at these magnitudes; this value applies both to ''random'' fields and to fields centered on known QSOs. The corresponding comoving space density is approximately half that of luminous (L greater than or similar to L*) present-day galaxies. Our sample of z > 3 galaxies is large enough that we can begin to detail the spectroscopic characteristics of the population as a whole. The spectra of the z > 3 galaxies are remarkably similar to those of nearby star-forming galaxies, the dominant features being strong low-ionization interstellar absorption lines and high-ionization stellar lines, often with P Cygni profiles characteristic of Wolf-Rayet and O star winds. Ly alpha emission is generally weak (less than 20 Angstrom rest equivalent width) and is absent for more than 50% of the galaxies. We assign approximate mass scales to the galaxies using the strengths of the heavily saturated interstellar features and find that, if the line widths are dominated by gravitational motions within the galaxies, the implied velocity dispersions are 180 km s(-1) less than or equal to sigma less than or equal to 320 km s(-1), in the range expected for massive galaxies. The star formation rates, which can be measured directly from the far-UV continua, lie in the range 4-25 h(50)(-2) M. yr(-1) (for q(0) = 0.5), with 8.5 h(50)(-2) M. yr(-1) being typical. Together with the morphological properties of the z > 3 galaxy population, which we discuss in a companion paper, all of these findings strongly suggest that we have identified the high-redshift counterparts of the spheroid component of present-day luminous galaxies. In any case, it is clear that massive galaxy formation was already well underway by z similar to 3.5.