Old English col "charcoal; live coal, piece of wood or other combustible substance, either burning or having been burned," from Proto-Germanic *kula(n) (source also of Old Frisian kole, Middle Dutch cole, Dutch kool, Old High German chol, German Kohle, Old Norse kol), from PIE root *g(e)u-lo- "live coal" (source also of Irish gual "coal").
Meaning "solid mineral consisting of fossilized carbon, combustible and used as fuel," is from mid-13c. The thing itself is mentioned 370 B.C.E. by Theophrastus in his treatise "On Stones" under the name lithos anthrakos (see anthrax). Traditionally good luck, coal was given as a New Year's gift in England, said to guarantee a warm hearth for the coming year.
The phrase drag (or rake) over the coals was a reference to the treatment meted out to heretics by Christians. To carry coals "do dirty work," also "submit to insult" is from 1520s.
To carry coals to Newcastle "add to that of which there is already an abundance, do unnecessary labor " (c. 1600) is a local variant on an ancient class of expression: Latin had in litus harenas fundere "pour sand on the beach," in silvam ligna ferre "carry wood to the woods;" Greek glauk eis Athenas "owls to Athens." Newcastle is in the midst of a great coal-producing region. The ancient view is not necessarily the modern one. A historian, noting that the medieval English exported manufactured cloth to the Low Countries, where weaving was a major industry, writes, "it is always sensible to send coals to Newcastle or owls to Athens if you can be sure of underselling the locals" [George D. Painter, "William Caxton," 1976]
"From 16th to 19th c. chiefly poetic, with associations of dignity, solemnity, or splendour ..." [OED]. Used in U.S. by 1826 of railway freight carriages and of passenger coaches on a railway by 1830; by 1862 of streetcars or tramway cars. Extension to "automobile" is by 1896, but from 1831 to the first decade of 20c. the cars meant "railroad train." Car bomb first attested 1972, in reference to Northern Ireland. The Latin word also is the source of Italian and Spanish carro, French char.