The first letter of mnemonic is a fossil. English has never pronounced the M, but it kept the spelling from Greek, where both consonants were spoken.
Merriam-Webster derives the word from Greek mnēmonikos, which comes from mnēmōn, "mindful," and from the verb mimnēskesthai, "to remember." Etymonline points to a related Greek noun, mnēmē, described as "memory as a mental faculty." Etymonline traces the family to an Indo-European root, men-, "to think," the same root behind English mind.
The dates are a little messy. Merriam-Webster gives 1672 for the first English adjective, meaning "assisting the memory." Etymonline gives 1753 and says the meaning "relating to memory" arrived in 1825, perhaps as a back-formation from mnemonics. The sources agree on the noun, a "mnemonic device," arriving in the 19th century. Merriam-Webster says 1842 and Etymonline says 1858.
The craft is far older than the word. A story passed on by Cicero credits the Greek poet Simonides, who lived from about 556 to 468 BC, with inventing the memory palace. At a banquet in Thessaly the roof reportedly fell in just after he stepped outside. He could name the crushed guests because he remembered where each had been sitting. From this, the story goes, he concluded that memory could be trained by attaching images to places. That is a legend, not documented history. Quintilian himself called the Castor and Pollux part of it fictitious, and ancient writers disagreed about the host's name. Roman orators did teach and use the technique, and the Stanford Encyclopedia of Philosophy describes how.
Mnemonic also has an opposite, and Etymonline records it. Amnemonic, "characterized by loss of memory," appeared in 1868, with the negating prefix a-. Another entry, antimnemonic (1817), means harmful to memory.
The word is also a small joke at its own expense. People remember "I before E, except after C" with a mnemonic, and Merriam-Webster uses that very rule as its example.