We show how rigidity emerges in experiments of sheared frictional granular materials by using generalizations of two methods for identifying rigid structures. Both approaches, the force-based dynamical matrix and the topology-based rigidity percolation, agree with each other and identify similar rigid structures. As the system becomes jammed, at a contact number of $z=2.4\pm 0.1$, a rigid backbone interspersed with floppy, particle-filled holes of a broad range of sizes emerges, creating a sponge-like morphology. We also find that the pressure within rigid structures always exceeds the pressure outside the rigid structures, i.e. that the backbone is load-bearing. These findings shows that it is necessary to go beyond mean-field theory to capture the physics of frictional jamming and also suggests that mechanical stability arises through arch structures and hinges at the mesoscale.