The short answer
The story is true and the quote is not — quite. In 1897, while Twain was in London, newspapers reported that he was gravely ill and then that he had died. He corrected the record, and the wording that appeared in the New York Journal on 2 June 1897 was simply that the report of his death was an exaggeration.
Where the famous version came from
His biographer Albert Bigelow Paine published an embellished account in 1912, two years after Twain's actual death, with the wording changed to a grosser exaggeration. From there the sentence kept inflating in circulation — reports rather than report, greatly rather than nothing at all — until it reached the form printed on posters today. Most scholarly quotation books now prefer the 1897 newspaper wording.
The shorter version is the better joke
This is why it is worth caring. Twain's actual line is deadpan: the report of my death was an exaggeration. Calling your own reported death merely an exaggeration is funny precisely because it is such a mild word for such an extreme error. Adding greatly explains the joke, and explaining a joke is how you kill it. The improved version is worse.
Twain saw this coming
In Following the Equator, published in November 1897 — the same year — Twain wrote that nearly any invented quotation, played with confidence, stands a good chance to deceive. He was, with some irony, describing his own future.
What this means for your English
There is a real lesson about understatement here. English humour often works by choosing a word that is too small for the situation — an exaggeration for a false death report, a bit chilly for freezing weather. It is called litotes or understatement, and using it well is one of the fastest ways to sound genuinely fluent rather than merely correct.