Recent high spatial and spectral resolution investigations of the diffuse interstellar medium (ISM) have found significant evidence for small-scale variations in the interstellar gas on scales less than or equal to 1 pc. To better understand the nature of small-scale variations in the ISM, we have used the KPNO WIYN Hydra multi-object spectrograph, which has a mapping advantage over the single-axis, single-scale limitations of studies using high proper motion stars and binary stars, to obtain moderate resolution (~12 km/s) interstellar Na I D absorption spectra of 172 stars toward the double open cluster h and Chi Persei. All of the sightlines toward the 150 stars with spectra that reveal absorption from the Perseus spiral arm show different interstellar Na I D absorption profiles in the Perseus arm gas. Additionally, we have utilized the KPNO Coude Feed spectrograph to obtain high-resolution (~3 km/s) interstellar Na I D absorption spectra of 24 of the brighter stars toward h and Chi Per. These spectra reveal an even greater complexity in the interstellar Na I D absorption in the Perseus arm gas and show individual components changing in number, velocity, and strength from sightline to sightline. If each of these individual velocity components represents an isolated cloud, then it would appear that the ISM of the Perseus arm gas consists of many small clouds. Although the absorption profiles vary even on the smallest scales probed by these high-resolution data (~30;~0.35pc), our analysis reveals that some interstellar Na I D absorption components from sightline to sightline are related, implying that the ISM toward h and Chi Per is probably comprised of sheets of gas in which we detect variations due to differences in the local physical conditions of the gas.