Paper-based sensors and assays have evolved rapidly due to the conversion of paper-based microfluidics, functional paper coatings, and new electrical and optical readout techniques. Nanomaterials have gained substantial attraction as key components in paper-based sensors, as they can be coated or printed relatively easily on paper to locally control the device functionality. Here, we report a new combination of methods to fabricate carbon nanotube-based (CNT) electrodes for paper-based electrochemical sensors using a combination of laser cutting, drop-casting, and origami. We applied this process to a range of filter papers with different porosities and used their differences in three-dimensional cellulose networks to study the influence of the cellulose scaffold on the final CNT network and the resulting electrochemical detection of glucose. We found that an optimal porosity exists, which balances the benefits of surface enhancement and electrical connectivity within the cellulose scaffold of the paper-based device and demonstrates a cost-effective process for the fabrication of device arrays.