1540s, "arrange (cargo) in a ship," from rummage (n.), 1520s, "act of arranging cargo in a ship," a shortening of French arrumage "arrangement of cargo," from arrumer "to stow goods in the hold of a ship," from a- "to" + rumer, probably from Germanic (compare Old Norse rum "compartment in a ship," Old High German rum "space," Old English rum; see room (n.)). Or else from English room (n.) + -age.
Meaning "to search closely (the hold of a ship), especially by moving things about" first recorded 1610s. Related: Rummaged; rummaging. Rummage sale (1803) originally was a sale at docks of unclaimed goods.