In this paper, we study the role of carboxymethyl cellulose (CMC) as a template for helping poly(3,4-ethylenedioxythiophene) (PEDOT) uniformly disperse into polyacrylamide (PAAM) hydrogel scaffold. The presence of a large amount of hydrogen bonds and chain entanglements enabled excellent mechanical properties with great stretchability and resilience. With the optimum mass loading of PEDOT (9.75 mg/cm2), a sandwiched configuration of flexible supercapacitor based on the CMC-PEDOT/PAAM hydrogel can deliver the highest specific capacitance of 269 mF/cm2, a maximum energy density of 23.93 μWh/cm2 at a power density of 400 μW/cm2 and remained 16.18 μWh/cm2 at a power density of 3200 μW/cm2, as well as enhanced cycle stability with 88% retention after 5000 cycles. In addition, such device can withstand severely bending and compressing deformations and properly operate at extreme temperatures (−40 ∼ 90 °C) with excellent capacitance property. What’s more, the excellent conductivity of the CMC-PEDOT/PAAM hydrogel contributed to outstanding strain sensing performances. When the supercapacitor was used to power the hydrogel strain sensor, the obtained self-powered sensing system is capable of monitoring physiological signals accurately. The multifunctional performance of the CMC-PEDOT/PAAM hydrogel could be potentially used in flexible electronic devices.