We explore the percolation threshold shift as short-range correlations are introduced and systematically varied in binary composites. Two complementary representations of the correlations are developed in terms of the distribution of phase bonds or, alternatively, using a set of appropriate short-range order parameters. In either case, systematic exploration of the correlation space reveals a boundary that separates percolating from nonpercolating structures and permits empirical equations that identify the location of the threshold for systems of arbitrary short-range correlation states. Two- and three-dimensional site lattices with two-body correlations, as well as a two-dimensional hexagonal bond network with three-body correlations, are explored. The approach presented here should be generalizable to more complex correlation states, including higher-order and longer-range correlations.