We present high-resolution (R approximate to 75,000), high signal-to-noise (S/N approximate to 100) Ca II lambda 3933.663 and Na I lambda lambda 5889.951, 5895.924 spectra of 68 stars in the direction of the Vela supernova remnant. The spectra comprise the most complete high-resolution, high S/N optical survey of early-type stars in this region of the sky. A subset of the sight lines has been observed at multiple epochs, 1993/1994 and 1996. Of the 13 stars observed twice, seven have spectra revealing changes in the equivalent width and/or velocity structure of lines, most of which arise from remnant gas. Such time variability has been reported previously for the sight lines toward HD 72089 and HD 72997 by Danks & Sembach and for HD 72127 by Hobbs and coworkers. We have confirmed the ongoing time variability of these spectra and present new evidence of variability in the spectra of HD 73658, HD 74455, HD 75309, and HD 75821. We have tabulated Na I and Ca II absorption-line information for the sight lines in our sample to serve as a benchmark for further investigations of the dynamics and evolution of the Vela SNR.