We present the first catalog and data release of the Swift-BAT AGN Spectroscopic Survey. We analyze optical spectra of the majority of the detected AGNs (77%, 642/836) based on their 14-195keV emission in the 70-month Swift-BAT all-sky catalog. This includes redshift determination, absorption and emission-line measurements, and black hole mass and accretion rate estimates for the majority of obscured and unobscured AGNs (74%, 473/642), with 340 measured for the first time. With ~90% of sources at z<0.2, the survey represents a significant advance in the census of hard X-ray-selected AGNs in the local universe. In this first catalog paper, we describe the spectroscopic observations and data sets, and our initial spectral analysis. The FWHMs of the emission lines show broad agreement with the X-ray obscuration (~94%), such that Sy 1-1.8 have N_H_<10^21.9^cm^-2^, and Seyfert 2 have N_H_>10^21.9^cm^-2^. Seyfert 1.9, however, show a range of column densities. Compared to narrow-line AGNs in the SDSS, the X-ray-selected AGNs have a larger fraction of dusty host galaxies (H{alpha}/H{beta}>5), suggesting that these types of AGN are missed in optical surveys. Using the [OIII]{lambda}5007/H{beta} and [NII]{lambda}6583/H{alpha} emission-line diagnostic, about half of the sources are classified as Seyferts; ~15% reside in dusty galaxies that lack an H{beta} detection, but for which the upper limits on line emission imply either a Seyfert or LINER, ~15% are in galaxies with weak or no emission lines despite high-quality spectra, and a few percent each are LINERS, composite galaxies, H II regions, or in known beamed AGNs.