In terms of things being mammoth, the noun predates the adjective by about 100 years; it comes from a Russian/Siberian word with common roots as the word meaning "earth" - since the remains were dug out of the ground and nobody ever saw the creatures walking around, it was assumed they lived underground like gigantic moles.
Mammoth teeth were first discovered in America in 1705, in New York. At first put forth as the tooth of a giant human, the true lineage began to become clear when similar fossils were found in South Carolina, and the people forced into slavery there recognized the similarity to elephant teeth. The Ohio River Valley also yielded bones and tusks, similar to ones being exhumed in Siberia. The first complete skeleton was assembled in 1802 by Charles Wilson Peale['s slave Moses Williams] and displayed in Philadelphia, to much public acclaim. It also captured the imagination of Thomas Jefferson.
In 1755, the French naturalist Count Georges-Louis Leclerc Buffon had written a book decrying the "degeneracy" of life on the American continent - its people were small and listless, he wrote, and it produced no animals comparable to those in the Old World. Because it was a new continent, still mostly swamp, and had not yet dried. (Seriously.) "No American animal can be compared with the elephant, the rhinoceros, the hippopotamus." This pissed the 6'2", Virginia-born Thomas Jefferson right the hell off. He took the time to assemble charts comparing American species with European ones, and when he went to France in 1784, he took a panther skin to show Buffon. And then mailed him a moose. So Jefferson, of course, was fascinated with the idea of the mammoth, a gigantic creature that could dwarf any produded by Europe.
Fun side fact: because people did not yet know that animals could go extinct (after all, if God had created all the animals on the sixth day, He would have no need to create new ones later and certainly would never allow one to disappear forever - thus if there are bones, there must be living animals that still have those bones inside them), one of the goals Jefferson set for the Lewis and Clark expedition was to find a living mammoth specimen. They did not succeed. Officially, at least.
Anyway, the exhibition of Peale's mammoth (which was actually a mastodon, but that's neither here nor there) was a total sensation, and people began using the word "mammoth" to describe anything large. Including a four-foot, 1,200-pound wheel of cheese the women of Cheshire, Massachusetts' Baptist church sent to? You guessed it, Thomas Jefferson.