We present very high resolution absorption measurements (R ∼ 150,000) of the interstellar Na I D lines at 5890 Å observed toward 19 early-type stars. The distances to these stars range from 20 to 220 pc, allowing a probe of the local interstellar medium (LISM). The velocity structure, velocity dispersions, and column densities of the various interstellar cloud components have been derived using an absorption-line fitting analysis. Most of the measured Na I absorption lines require two distinct cloud components for an adequate fit. Sodium column densities have been determined toward 10 of the target stars. No sodium absorption was detected toward any of the stars with distances less than 42 pc. These null results imply a corresponding hydrogen column density limit, N(H), of ∼ 2.5 × 1018 cm-2 in many directions in the LISM. For two exceptionally vacant lines of sight (to β CMa and 36 Lyn), this limit of low hydrogen column density can be placed out to much larger distances. A comparison of the measured sodium columns with those of interstellar Ca II indicates that for stars closer than 95 pc the ratio Na I/Ca II is less than 0.5. This value is consistent with the presence of gas at T ∼ 8000 K and an electron density, ne, of 0.03 cm-3 in the LISM. At distances beyond 100 pc the Na I/Ca II ratio is greater than 1.0, which is expected for normal, diffuse, cold interstellar clouds.