Know how to use "fewer" and "less"? Find out.
1806, originally was a military drill to teach balance; "to stand on each leg alternately and swing the other back and forth" (which, presumably, reminded someone of a goose's way of walking); in reference to "marching without bending the knees" (as in Nazi military reviews) it apparently is first recorded 1916. As a verb by 1854.
Note: The term is sometimes used to suggest the unthinking loyalty of followers or soldiers: “Brown has a goose-step mentality.”