The development of flexible and wearable sensors in the past decade has made them have good application prospects in personalized medicine, human-computer interaction and intelligent robots. Flexible conductive polymer composite materials composed of conductive materials and elastic polymers, which have high stretchability, excellent flexibility, durability and other characteristics, can be used to prepare flexible sensors with wide sensing range and high sensitivity. This article reviews the composite types (filled type strain sensors, sandwich type strain sensors, adsorption type strain sensors) and sensing mechanisms (tunneling effect, disconnection mechanism, crack propagation) of stretchable strain sensors based on flexible conductive polymer composite materials. The structure design of the composite materials used for the sensor is introduced in detail, including the internal structure (double percolation structure, segregation structure, porous structure, and “brick-and-mortar” structure), surface structure (wrinkles structure and microcrack structure) and macro structure (fiber structure, net structure, film structure). The internal structure design can reduce the materials’ percolation threshold, the surface structure design can improve the sensor performance, and each macro structure has its own characteristics. Finally, the developments of the sensors in material selection, preparation technology, structure design, compound mode, additional performance and application direction are prospected.