High electrical conductivity, along with high piezoresistive sensitivity and stretchability, are crucial for designing and developing nanocomposite strain sensors for damage sensing and on-line structural health monitoring of smart carbon fiber-reinforced polymer (CFRP) composites. In this study, the influence of the geometric features and loadings of carbon-based nanomaterials, including reduced graphene oxide (rGO) or carbon nanofibers (CNFs), on the tunable strain-sensing capabilities of epoxy-based nanocomposites was investigated. This work revealed distinct strain-sensing behavior and sensitivities (gauge factor, GF) depending on both factors. The highest GF values were attained with 0.13 wt.% of rGO at various strains. The stability and reproducibility of the most promising self-sensing nanocomposites were also evaluated through ten stretching/relaxing cycles, and a distinct behavior was observed. While the deformation of the conductive network formed by rGO proved to be predominantly elastic and reversible, nanocomposite sensors containing 0.714 wt.% of CNFs showed that new conductive pathways were established between neighboring CNFs. Based on the best results, formulations were selected for the manufacturing of pre-impregnated materials and related smart CFRP composites. Digital image correlation was synchronized with electrical resistance variation to study the strain-sensing capabilities of modified CFRP composites (at 90° orientation). Promising results were achieved through the incorporation of CNFs since they are able to form new conductive pathways and penetrate between micrometer-sized fibers.