We present results of an optical search conducted as part of the SH0ES project (Supernovae and H-0 for the Equation of State of dark energy) for Cepheid variable stars using the Hubble Space Telescope (HST) in 19 hosts of Type Ia supernovae (SNe Ia) and the maser-host galaxy NGC 4258. The targets include nine newly imaged SN. Ia hosts using a novel strategy based on a long-pass filter that minimizes the number of HST orbits required to detect and accurately determine Cepheid properties. We carried out a homogeneous reduction and analysis of all observations, including new universal variability searches in all SN. Ia hosts, which yielded a total of 2200 variables with well-defined selection criteria, the largest such sample identified outside the Local Group. These objects are used in a companion paper to determine the local value of H-0 with a total uncertainty of 2.4%.