Understanding how disks dissipate is essential to studies of planet formation. However, identifying exactly how dust and gas dissipate is complicated due to the difficulty of finding objects that are clearly in the transition phase of losing their surrounding material. We use Spitzer Infrared Spectrograph (IRS) spectra to examine 35 photometrically selected candidate cold disks (disks with large inner dust holes). The infrared spectra are supplemented with optical spectra to determine stellar and accretion properties and 1.3 mm photometry to measure disk masses. Based on detailed spectral energy distribution modeling, we identify 15 new cold disks. The remaining 20 objects have IRS spectra that are consistent with disks without holes, disks that are observed close to edge-on, or stars with background emission. Based on these results, we determine reliable criteria to identify disks with inner holes from Spitzer photometry, and examine criteria already in the literature. Applying these criteria to the c2d surveyed star-forming regions gives a frequency of such objects of at least 4% and most likely of order 12% of the young stellar object population identified by Spitzer. We also examine the properties of these new cold disks in combination with cold disks from the literature. Hole sizes in this sample are generally smaller than in previously discovered disks and reflect a distribution in better agreement with exoplanet orbit radii. We find correlations between hole size and both disk and stellar masses. Silicate features, including crystalline features, are present in the overwhelming majority of the sample, although the 10 μm feature strength above the continuum declines for holes with radii larger than ~7 AU. In contrast, polycyclic aromatic hydrocarbons are only detected in 2 out of 15 sources. Only a quarter of the cold disk sample shows no signs of accretion, making it unlikely that photoevaporation is the dominant hole-forming process in most cases.