We present a new technique, multiepoch observations of 21 cm absorption against high-velocity pulsars, to probe the properties of the cold neutral hydrogen gas (H I) in the interstellar medium (ISM) at AU scales. In three epochs, over a 1.7 yr interval, we find evidence for significant opacity variations toward all of the pulsars in our sample. Small-scale structure in the ISM is detected on a range of scales from 5 AU to 100 AU, over a wide range of distances (50-2600 pc), opacities (tau(max) = 0.1-2.5) and directions (anticenter, interarm, high latitude, and local ISM). It appears that small-scale structure is a general property of the ISM and is not confined to special lines of sight. A significant fraction (10%-15%) of the cold H I gas is in this form. These opacity variations do not show any strong correlations with such parameters as transverse distance or integrated opacity, and there is no obvious relation between these structures and those seen in the ionized phase of the ISM.