Synthetic methods to produce electrochemically exfoliated graphite (EEG) and composites containing silver nanoparticles (AgNPs) deposited on the EEG surface are discussed. An aqueous solution KIO3 was used as the electrolyte for the first time; therefore, oxidation and exfoliation mechanisms are described and discussed in detail. The graphite-based nanostructures were characterized by high stability in water and ethanol dispersions. Two composites with spherical or hollow-shaped ultra-fine AgNPs were synthesized and their structure and physicochemical properties are described. Use of CaCl2 with NaBH4 resulted in the formation of hollow nanoparticles on the EEG surface, whereas simple photoreduction synthesized ultra-fine nanoparticles. The role of silver nanoparticles attached to EEG on the gas sensing properties (for NO2) at different temperatures was determined. Gas sensing experiments confirmed that relatively low levels of AgNPs (1.36% and 6.16% for hollow and spherical NPs, respectively) improved the NO2 sensing properties of EEG. Moreover, at higher temperatures (150 °C) and relatively high NO2 concentrations (>50 ppm), the conductivities of both composites switched from p-type to n-type. The composite with a lower nanoparticle loading (1.56 at%) but larger size showed a significantly better dynamic parameters (response and recovery time).