Origami structures with a large number of excess folds are capable of storing distinguishable geometric states that are energetically equivalent. As the number of excess folds is reduced, the system has fewer equivalent states and can eventually become rigid. We quantify this transition from a floppy to a rigid state as a function of the presence of folding constraints in a classic origami tessellation, Miura-ori. We show that in a fully triangulated Miura-ori that is maximally floppy, adding constraints via the elimination of diagonal folds in the quads decreases the number of degrees of freedom in the system, first linearly and then nonlinearly. In the nonlinear regime, mechanical cooperativity sets in via a redundancy in the assignment of constraints, and the degrees of freedom depend on constraint density in a scale-invariant manner. A percolation transition in the redundancy in the constraints as a function of constraint density suggests how excess folds in an origami structure can be used to store geometric information in a scale-invariant way.