1530s, earliest in English in an obsolete sense "cover or bag for clothes," from French toilette "a cloth; a bag for clothes," diminutive of toile "cloth, net" (see toil (n.2)). Toilet acquired an association with upper class dressing by 18c., through the specific sense "a fine cloth cover on the dressing table for the articles spread upon it;" thence "the articles, collectively, used in dressing" (mirror, bottles, brushes, combs, etc.). Subsequent sense evolution in English (mostly following French uses) is to "act or process of dressing," especially the dressing and powdering of the hair (1680s); then "a dressing room" (1819), especially one with a lavatory attached; then "lavatory or porcelain plumbing fixture" (1895), an American euphemistic use.
Toilet paper is attested from 1884 (the Middle English equivalent was arse-wisp). Toilet training is recorded from 1940.