We report on spectroscopic observations covering most of the 475 BL Lacs in the second Fermi Large Area Telescope (LAT) catalog of active galactic nuclei (AGNs). Including archival measurements (correcting several erroneous literature values) we now have spectroscopic redshifts for 44% of the BL Lacs. We establish firm lower redshift limits via intervening absorption systems and statistical lower limits via searches for host galaxies for an additional 51% of the sample leaving only 5% of the BL Lacs unconstrained. The new redshifts raise the median spectroscopic z from 0.23 to 0.33 and include redshifts as large as z = 2.471. Spectroscopic redshift minima from intervening absorbers have z = 0.70, showing a substantial fraction at large z and arguing against strong negative evolution. We find that detected BL Lac hosts are bright ellipticals with black hole masses M sub( times ) ~ 10 super(8.5)-10 super(9), substantially larger than the mean of optical AGNs and LAT Flat Spectrum Radio Quasar samples. A slow increase in M sub( times ) with z may be due to selection bias. We find that the power-law dominance of the optical spectrum extends to extreme values, but this does not strongly correlate with the gamma -ray properties, suggesting that strong beaming is the primary cause of the range in continuum dominance.