1530s, "thing that rubs" (a brush, cloth, etc.), agent noun from rub (v.). By c. 1600 as "one who applies friction or massage in some process."
The meaning "elastic substance from tropical plants" is recorded by 1788, short for India rubber. Earlier known also as catouchou, caoutchouc, it was introduced to Europe 1744 by Charles Marie de la Condamine, so called because it originally was used to erase pencil marks from paper, etc. Later extended to synthetic substances having the same qualities.
This substance is very useful in drawing, &c., for erasing the strokes of black lead pencils, and is popularly called rubber, and lead-eater. [from the entry for Caoutchouc in George Selby Howard, "New Royal Cyclopaedia," 1788]
The meaning "an overshoe made of rubber" is 1842, American English; slang sense of "contraceptive sheath, condom" is by 1930s. As an adjective by 1844, "In very common use from about 1875" [OED]. Some figurative phrases are from the notion of rubber automobile tires.
Rubber cement "adhesive compound containing rubber" is attested from 1856 (from 1823 as India-rubber cement). Rubber check (one that "bounces") is from 1927. The decorative household rubber plant is so called by 1876 (earlier India-rubber plant, by 1805). Rubber-chicken circuit "after-dinner speaking tour" is by 1959, in reference to the likely quality of the food.
"deciding match" in a game or contest, usually a third where each has won one, 1590s, a word of unknown origin and signification; even the original form is uncertain. Not obviously connected to rubber (n.1).