The fabrication concept for a low-cost sensor device using reduced graphene oxide (rGO) as the sensing material on a porous paper substrate is presented. The sensors were characterized using conductivity and capacitance measurements, atomic force microscopy and X-ray photoelectron spectroscopy. The effects of different reducing agents, graphene oxide (GO) flake size and film thickness were studied. The sensor was sensitive to NO2, and devices based on a thin (10-nm) hydrazine-reduced GO layer had the best sensitivity, reaching a 70% reduction in resistance after 10 min of exposure to 10 ppm NO2. The sensitivity was high enough for the detection of sub-parts per million levels of NO2. Desorption of gas molecules, i.e. the recovery of the sensor, could be accelerated by UV irradiation. The structure and preparation of the sensor are simple and up-scalable, allowing their fabrication in bulk quantities, and the fabrication concept can be applied to other materials, too.