We present optical spectroscopy of 62 objects selected from several samples of ultra steep spectrum (USS) radio sources. 46 of these are from our primary catalog, consisting of 669 sources with radio spectral indices alpha < -1.30 (S_nu ~ nu^alpha); this first spectroscopic sub-sample was selected on the basis of their faint optical and near-IR identifications. Most are identified as narrow-lined radio galaxies with redshifts ranging from z=0.25 to z=5.19. Ten objects are at z>3, nearly doubling the number of such sources known to date. Four of the USS radio sources are identified with quasars, of which at least three have very red spectral energy distributions. The source TN J0936-2242 is identified with an extremely red object (ERO, R-K>5); both it and a close companion are at z=1.479. The spectrum of the ERO closely resembles that of previously discovered radio galaxies at z~1.5. Five sources show continuum emission, but fail to show any clear emission or absorption features, despite integrations of ~1 h with the Keck telescope. We suggest that these objects could be (i) radio galaxies with faint emission lines in the ``redshift desert at 1.5 <~ z <~ 2.3, (ii) radio galaxies with an obscured AGN, which are dominated by a stellar continuum observed with insufficient S/N, or (iii) pulsars. Three radio sources identified with faint objects in the K-band images remain undetected in 50-90 min spectroscopic integrations with the Keck telescope, and are possible z>7 candidates.