We report on a large Hubble Space Telescope imaging survey of BL Lac objects, at spatial resolution >~10 times better than previous ground-based surveys. We focus on data reduction and analysis, describing the procedures used to model the host galaxy surface brightness radial profiles. A total of 69 host galaxies were resolved out of 110 objects observed, including almost all sources at z<~0.5. We classify them morphologically by fitting with either an exponential disk or a de Vaucouleurs profile; when one fit is preferred over the other, in 58 of 69 cases, it is invariably the elliptical morphology. This is a very strong result given the large number of BL Lac objects, the unprecedented spatial resolution, and the homogeneity of the data set. With the present reclassification of the host galaxy of 1418+546 as an elliptical, there remain no undisputed examples of a disk galaxy hosting a BL Lac nucleus. This implies that, at 99% confidence, fewer than 7% of BL Lac objects can be in disk galaxies. The apparent magnitude of the host galaxies varies with distance as expected if the absolute magnitudes are approximately the same, with a spread of +/-1 mag, out to redshift z~0.5. At larger redshifts, only six of 23 BL Lac objects are resolved so the present data do not constrain possible luminosity evolution of the host galaxies. The collective Hubble diagram for BL Lac host galaxies and radio galaxies strongly supports their unification.