We show how rigidity emerges in experiments on sheared two-dimensional 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 critical contact number z_{c}=2.4±0.1, a rigid backbone interspersed with floppy, particle-filled holes of a broad range of sizes emerges, creating a spongelike morphology. While the pressure within rigid structures always exceeds the pressure outside the rigid structures, they are not identified with the force chains of shear jamming. These findings highlight the need to focus on mechanical stability arising through arch structures and hinges at the mesoscale.