We report an entirely new class of printed electrical gas sensors that are produced at near 'zero cost'. This technology exploits the intrinsic hygroscopic properties of cellulose fibers within paper; although it feels and looks dry, paper contains substantial amount of moisture, adsorbed from the environment, enabling the use of wet chemical methods for sensing without manually adding water to the substrate. The sensors exhibit high sensitivity to water soluble gases (e.g., limit-of-detection for NH3 <200 parts-per-billion) with a fast and reversible response. The sensors show comparable or better performance (especially at high relative humidity) than most commercial ammonia sensors at a fraction of their price (<$0.02 per sensor). We demonstrate that the sensors proposed can be integrated into food packaging to monitor freshness (to reduce food waste and plastic pollution) or implemented into near-field-communication tags to function as wireless, battery-less gas sensors that can be interrogated with smartphones.