1933, American English, from super- + market (n.). The 1933 reference is in an article that says the stores themselves began to open around 1931. An early word for a "superstore" was hypermarket (1967).
superintendent
superior
superiority
superlative
superman
supermarket
supermodel
supernal
supernatant
supernatural
supernaturally