We have conducted a directed search for intergalactic H I clouds, using H II galaxies as pointers to fields on the sky likely to contain such clouds. This extends our previous survey (Taylor et al. 1993) by using the VLA to map in the 21 cm line of H I a complete, volume-limited sample of H II galaxies. We detected 20 of the 21 galaxies in our sample and find that 14 have nearby H I companions. Some H II galaxies have multiple companions, and we have discovered a total of 19 companions, or a frequency of occurrence of companions of 0.67. This detection rate is statistically consistent with a lower limit of the companion frequency of 0.46, assuming that no companions are present outside of the spatial and velocity ranges searched by our VLA observations. The companion population is not a homogeneous one but is comprised of H II galaxies, cataloged and previously uncataloged dwarfs, and several objects for which there are no known optical counterparts. These latter objects may be intergalactic H I clouds. Here we present our H I maps and R-band optical images of the H II galaxy and companion systems, along with physical properties determined from these data. We compare our sample to samples of H II galaxies from the literature, finding that the literature samples over-represent the more massive, more luminous H II galaxies. Our total mass estimates imply that H II galaxies are dominated by dark matter, in agreement with observations of dwarf irregular galaxies. We also find a tendency for H II galaxies to be characterized by dense central H I concentrations surrounded by less dense envelopes. Detailed analysis of the H II galaxy/companion systems will appear in subsequent papers.