This is the second in a series of papers presenting observations and results for a sample of 76 ultra-steep-spectrum (USS) radio sources in the southern hemisphere designed to find galaxies at high redshift. Here we focus on the optical spectroscopy program for 53 galaxies in the sample. We report 35 spectroscopic redshifts, based on observations with the Very Large Telescope (VLT), the New Technology Telescope (NTT) and the Australian National Universitys 2.3m telescope; they include five radio galaxies with z>3. Spectroscopic redshifts for the remaining 18 galaxies could not be confirmed: three are occulted by Galactic stars, eight show continuum emission but no discernible spectral lines, whilst the remaining seven galaxies are undetected in medium-deep VLT integrations. The latter are either at very high redshift (z >~7) or heavily obscured by dust. A discussion of the efficiency of the USS technique is presented. Based on the similar space density of z>3 radio galaxies in our sample compared with other USS-selected samples, we argue that USS selection at 843-1400 MHz is an efficient and reliable technique for finding distant radio galaxies.