Using first-principles calculations within density functional theory, we explore systematically the capacity of charged carbon fullerenes Cn (20 <or= n <or= 82) as hydrogen storage media. We find that the binding strength of molecular hydrogen on either positively or negatively charged fullerenes can be dramatically enhanced to 0.18-0.32 eV, a desirable range for potential room-temperature, near ambient applications. The enhanced binding is delocalized in nature, surrounding the whole surface of a charged fullerene, and is attributed to the polarization of the hydrogen molecules by the high electric field generated near the surface of the charged fullerene. At full hydrogen coverage, these charged fullerenes can gain storage capacities of up to approximately 8.0 wt %. We also find that, contrary to intuitive expectation, fullerenes containing encapsulated metal atoms only exhibit negligible enhancement in the hydrogen binding strength, because the charge donated by the metal atoms is primarily confined inside the fullerene cages. These predictions may prove to be instrumental in searching for a new class of high-capacity hydrogen storage media.