[Abridged] We present maps of CO 2-1 emission covering the entire star-forming disks of 16 nearby dwarf galaxies observed by the IRAM HERACLES survey. The data have 13 arcsec angular resolution, ~250 pc at our average distance of 4 Mpc, and sample the galaxies by 10-1000 resolution elements. We apply stacking techniques to perform the first sensitive search for CO emission in dwarfs outside the Local Group ranging from single lines-of-sight, stacked over IR-bright regions of embedded star formation, and stacked over the entire galaxy. We detect 5 dwarfs in CO with total luminosities of L_CO = 3-28 1e6 Kkmspc2. The other 11 dwarfs remain undetected in CO even in the stacked data and have L_CO < 0.4-8 1e6 Kkmspc2. We combine our sample of dwarfs with a large literature sample of spirals to study scaling relations of L_CO with M_B and metallicity. We find that dwarfs with metallicities of Z ~ 1/2-1/10 Z_sun have L_CO about 1e2-1e4x smaller than spirals and that their L_CO per unit L_B is 10-100x smaller. A comparison with tracers of star formation (FUV and 24 micron) shows that L_CO per unit SFR is 10-100x smaller in dwarfs. One possible interpretation is that dwarfs form stars much more efficiently, however we argue that the low L_CO/SFR ratio is due to significant changes of the CO-to-H2 conversion factor, alpha_CO, in low metallicity environments. Assuming a constant H2 depletion time of 1.8 Gyr (as found for nearby spirals) implies alpha_CO values for dwarfs with Z ~ 1/2-1/10 Z_sun that are more than 10x higher than those found in solar metallicity spirals. This significant increase of alpha_CO at low metallicity is consistent with previous studies, in particular those which model dust emission to constrain H2 masses. Even though it is difficult to parameterize the metallicity dependence of alpha_CO, our results suggest that CO is increasingly difficult to detect at lower metallicities.