1802, in military writing, to describe a very tight style of mass marching, from lock (n.1) + step (n.).
Lock-step. A mode of marching by a body of men going one after another as closely as possible, in which the leg of each moves at the same time with and closely follows the corresponding leg of the person directly before him. [Thomas Wilhelm, "Military Dictionary and Gazetteer," Philadelphia, 1881]
Figurative use by 1836.