"stone in the middle of an arch (typically the uppermost stone), which holds up the others," 1630s, earlier simply key (1520s), from key (n.1) in figurative sense of "that which holds together other parts," or from its Middle English architectural sense "projecting ornament of at the intersections of ribs of vaulted or flat ceilings" (mid-14c.). Being the last put in, it is regarded as "keying," or locking together, the whole structure.
Figurative sense "chief element of a system" is from 1640s. Pennsylvania was called the Keystone State because of its position (geographical and political) in the original American confederation, occupying the middle (7th) place in the "arch" of states along the Atlantic, between eastern states and southern ones. Keystone cops were the bumbling police in the slapstick silent movies produced by Keystone Studios, formed in 1912 in Edendale, Calif., by Canadian-born U.S. film director Mack Sennett (1884-1960).