Boolean networks, widely used to model gene regulation, exhibit a phase transition between regimes in which small perturbations either die out or grow exponentially. We show and numerically verify that this phase transition in the dynamics can be mapped onto a static percolation problem which predicts the long-time average Hamming distance between perturbed and unperturbed orbits.