Electroactive composite materials are very promising for musculoskeletal tissue engineering because they can be applied in combination with electrostimulation. In this context, novel graphene-based poly(3-hydroxybutyrate-co-3-hydroxyvalerate)/polyvinyl alcohol (PHBV/PVA) semi-interpenetrated networks (semi-IPN) hydrogels were engineered with low amounts of graphene (G) nanosheets dispersed within the polymer matrix to endow them with electroactive properties. The nanohybrid hydrogels, obtained by applying a hybrid solvent casting–freeze-drying method, show an interconnected porous structure and a high water-absorption capacity (swelling degree > 1200%). The thermal characterization indicates that the structure presents microphase separation, with PHBV microdomains located between the PVA network. The PHBV chains located in the microdomains are able to crystallize; even more after the addition of G nanosheets, which act as a nucleating agent. Thermogravimetric analysis indicates that the degradation profile of the semi-IPN is located between those of the neat components, with an improved thermal stability at high temperatures (>450 °C) after the addition of G nanosheets. The mechanical (complex modulus) and electrical properties (surface conductivity) significantly increase in the nanohybrid hydrogels with 0.2% of G nanosheets. Nevertheless, when the amount of G nanoparticles increases fourfold (0.8%), the mechanical properties diminish and the electrical conductivity does not increase proportionally, suggesting the presence of G aggregates. The biological assessment (C2C12 murine myoblasts) indicates a good biocompatibility and proliferative behavior. These results reveal a new conductive and biocompatible semi-IPN with remarkable values of electrical conductivity and ability to induce myoblast proliferation, indicating its great potential for musculoskeletal tissue engineering.