We present maps of (12)COJ = 2-1 emission covering the entire star-forming disks of 16 nearby dwarf galaxies observed by the IRAM HERACLES survey. The data have 13 '' angular resolution, similar to 250 pc at our average distance of D = 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 dwarf galaxies outside the Local Group ranging from individual lines of sight, stacking over IR-bright regions of embedded star formation, and stacking over the entire galaxy. We detect five galaxies in CO with total CO luminosities of LCO2-1 = (3-28) x 10(6) K km s(-1) pc(2). The other 11 galaxies remain undetected in CO even in the stacked images and have LCO2-1 less than or similar to (0.4-8) x 10(6) K km s(-1) pc(2). We combine our sample of dwarf galaxies with a large sample of spiral galaxies from the literature to study scaling relations of L-CO with M-B and metallicity. We find that dwarf galaxies with metallicities of Z approximate to 1/2-1/10 Z(circle dot) have L-CO of 2-4 orders of magnitude smaller than massive spiral galaxies and that their L-CO per unit L-B is 1-2 orders of magnitude smaller. A comparison with tracers of star formation (FUV and 24 mu m) shows that L-CO per unit star formation rate (SFR) is 1-2 orders of magnitude smaller in dwarf galaxies. One possible interpretation is that dwarf galaxies form stars much more efficiently: we argue that the low L-CO/SFR ratio is due to the fact that the CO-to-H-2 conversion factor, alpha(CO), changes significantly in low-metallicity environments. Assuming that a constant H-2 depletion time of tau(dep) = 1.8 Gyr holds in dwarf galaxies (as found for a large sample of nearby spirals) implies alpha(CO) values for dwarf galaxies with Z approximate to 1/2-1/10 Z(circle dot) that are more than one order of magnitude higher than those found in solar metallicity spiral galaxies. Such a significant increase of alpha(CO) at low metallicity is consistent with previous studies, in particular those of Local Group dwarf galaxies that model dust emission to constrain H2 masses. Even though it is difficult to parameterize the dependence of aCO on metallicity given the currently available data, the results suggest that CO is increasingly difficult to detect at lower metallicities. This has direct consequences for the detectability of star-forming galaxies at high redshift, which presumably have on average sub-solar metallicity.