1550s, "a coarse, heavy, woolen fabric," a word of Scandinavian origin; compare Norwegian dialectal rugga "coarse coverlet," from Old Norse rogg "shaggy tuft," from Proto-Germanic *rawwa-. Perhaps it is related to rag (n.1) and rough (adj.), and compare rugged.
The original meaning is obsolete. The sense evolved or expanded to "thick coverlet or lap-robe, heavy woolen wrap" used for various purposes (1590s), then "mat for the floor" (by 1808). The meaning "toupee" is theater slang attested by 1940.
To cut a rug "dance" is slang attested by 1942 (rug-cutter "expert dancer" is recorded by 1938). To sweep or brush something under the rug in the figurative sense of "conceal in hopes it won't be noticed or remembered" is by 1954. Figurative expression pull the rug out from under (someone) "suddenly deprive of important support" is from 1936, American English. Earlier in same sense was cut the grass under (one's) feet (1580s).