To address the engineering challenges associated with the high brittleness and poor crack resistance of coal-based solid waste grouting materials, this study systematically investigates the flexural performance and damage evolution characteristics of the material by incorporating various types and amounts of fibers into a matrix composed of coal gangue, fly ash, Portland cement, and sulfoaluminate cement. Macroscopic mechanical testing, digital image correlation (DIC) technology, and scanning electron microscopy (SEM) are employed to reveal the mechanisms by which fibers influence the grouting material. The results demonstrate that fiber type and dosage significantly affect the flexural strength and damage evolution behavior of the material. Among them, basalt fiber exhibits the most pronounced improvement in flexural strength at a dosage of 0.4%, achieving a 28-day flexural strength of 6.33 MPa, which is 73.9% higher than that of the control group. Similarly, glass fiber shows a flexural strength increase of 63.18% at a dosage of 0.8%. The fibers enhance the material’s ductility and promote the uniformity of the failure process through mechanisms such as crack bridging, energy dissipation, and optimized interfacial structure. Furthermore, joint analysis using DIC and acoustic emission (AE) techniques reveals that when the fiber dosage reaches 0.6%, the proportion of shear cracks during material failure significantly increases (12.78–16.13%), indicating that fibers improve the uniformity of strain distribution under loading, delay the propagation of the main crack, and thereby enhance the overall crack resistance of the material. These findings provide theoretical and technical support for the development of high-toughness and high-performance coal-based solid waste grouting materials.