Carbon materials such as carbon nanotubes (CNTs), graphene, and reduced graphene oxide (RGO) exhibit unique electrical properties, which are also influenced by the surrounding atmosphere. They are therefore promising sensing materials. Despite the existence of studies reporting the gas-sensing properties of metal oxide (MOx) coated nanostructured carbon, an incomplete understanding of their sensing mechanism remains. Here we report a systematic study on the preparation, characterization, and sensing properties of CNT and RGO composites with SnO2 coating. Atomic layer deposition (ALD) was applied to the conformal coating of the inner and outer walls of CNTs with thin films of SnO2 of various thicknesses, while nonaqueous sol–gel chemistry assisted by microwave heating was used to deposit tin dioxide onto RGO in one step. The sensing properties of SnO2/CNTs and SnO2/RGO heterostructures toward NO2 target gas were investigated as a function of the morphology and density of the metal oxide coating. The general sensing mechanism of carbon-based heterostructures and the role of the various junctions involved are established.