from Old English gang "a going, journey, way, passage," and Old Norse gangr "a group of men, a set," both from Proto-Germanic *gangaz (source also of Old Saxon, Old Frisian, Danish, Dutch, Old High German, German gang, Old Norse gangr, Gothic gagg "act of going"), of uncertain origin, perhaps from PIE root *ghengh- "to step" (source also of Sanskrit jangha "shank," Avestan zanga- "ankle," Lithuanian žengiu "I stride"). Not considered to be related to go.
The sense evolution is probably via meaning "a set of articles that usually are taken together in going" (mid-14c.), especially a set of tools used on the same job. By 1620s this had been extended in nautical speech to mean "a company of workmen," and by 1630s the word was being used, with disapproving overtones, for "any band of persons traveling together," then "a criminal gang or company" (gang of thieves, gang of roughs, etc.). By 1855 gang was being used in the sense "group of criminal or mischievous boys in a city." In American English, especially of slaves working on plantations (1724). Also formerly used of animal herds or flocks (17c.-19c.). Gangway preserves the original sense of the word, as does gang-plank.