We utilize Sloan Digital Sky Survey imaging and spectroscopy of 653,000 star-forming galaxies at z60.1 to study the relation between stellar mass and gas-phase metallicity. We derive gas-phase oxygen abundances and stellar masses using new techniques that make use of the latest stellar evolutionary synthesis and photoionization models. We find a tight (c0.1 dex) correlation between stellar mass and metallicity spanning over 3 orders of magnitude in stellar mass and a factor of 10 in metallicity. The relation is relatively steep from 10 super(8.5) to 10 super(10.5) M sub( )h70 super(-2), in good accord with known trends between luminosity and metallicity, but flattens above 10 super(10.5) M sub( ). We use indirect estimates of the gas mass based on the Ha luminosity to compare our data to predictions from simple closed box chemical evolution models. We show that metal loss is strongly anticorrelated with baryonic mass, with low-mass dwarf galaxies being 5 times more metal depleted than L* galaxies at z60.1. Evidence for metal depletion is not confined to dwarf galaxies but is found in galaxies with masses as high as 10 super(10) M sub( ). We interpret this as strong evidence of both the ubiquity of galactic winds and their effectiveness in removing metals from galaxy potential wells.