Perhaps he was just the first Dane to use it. I guess in older times, you could get credit for a quote if you were the first in a country to use it. From http://quoteinvestigator.com/2012/04/28/shorter-letter/ it looks like Benjamin Franklin was among the first Americans. But then again, what can we really trust?
Maybe we should just attribute all quotes to Mark Twain and be done with it.
Textual evidence. The first demonstrable text wins, until an earlier is found. Sometimes it's fuzzy, because quotes morph (they get pithier over time). But most of the time it's clear enough, and the techniques for studying it are well understood.
Edit: The same is true in reverse, too: if a famous person really said X, it will be easy to find a precise textual source for X by googling. I don't mean a website claiming they said it (those are legion), but the original text, e.g. from their collected works, or an original newspaper interview. Since they're famous, that territory will have been trodden many times and there will be websites linking to it. Therefore if you can't find it, the famous person probably didn't say it. “Absence of evidence is evidence of absence” (hey, I wonder who said that one?) really works in this case.
Much like how, when one is in doubt in math, one just calls it Euler's theorem.