Sorry, Portugal
Considering a post about arigatou [gozaimasu] came from, I decided to first google to make sure I wasn't duplicating anyone else's work. Unfortunately I didn't get very far into the search results, because most of them were about the folk etymology: that it's from Portuguese obrigado. This is wrong, wrong, wrong.
Arigatou is the Western Japanese way of saying arigataku, the adverbial form (more or less) of arigatai. The basic rule is replacing ku with u, but in this case that produced au, which becomes ou (→ a lengthened o) through the magic of sound change. This also happened to omedetou (← (o)medetai) and ohayou (← (o)hayai). (It is not a coincidence that despite the Tokyo version getting "Standard Japanese" status, the standard politeness terms were imported from the old Imperial capital!)
Another common example of ku → u is in tou ni, which coexists with toku ni and means "already" or "long ago". (Both of them come from toshi (疾し), an OJ adjective meaning "vigorous" or "fast" or "early".) You can hear a tou ni at the end of every chorus in KAJI Meiko's song The Flower of Carnage on the Kill Bill soundtrack.
So, given that gozaimasu is a Sino-hoity-toity form of aru, arigatou gozaimasu breaks down to arigataku aru: "to exist arigatai-ly". Arigatai is ari-gatai: to be, to exist (ari) + to be difficult to do (-gatai, probably related to katai, to be (physically) hard).
But using this to mean "I thank you", i.e. "It is difficult/rare for [such kindness as yours] to exist", is a relatively recent development. The form ari + gatai has been around (as arigatashi, of course) since Manyoushuu times, which in Japanese linguistics means "forever". In that poem it just means "unlikely to be". It can also be found sprinkled throughout Heian literature meaning "rare" or "difficult" without any special connection to the idea of gratitude.
The generally accepted theory about the "thank you" usage is that it derives from the Buddhist community, sometime in the middle of the second millennium, and in fact the Lotus Sutra is often mentioned as a source of the phrase itself (specifically, the part in the parable of the burning house where the father says "汝等所可玩好希有難得..."). I have no idea whether this is true or not, though. (UPDATE: It probably ain't. See comments.)
Oh, and knowing this makes the doumo seem a lot more sensible. "No matter what, it is difficult for [such kindness] to exist..."
Bonus information: omedetai comes from o (politeness prefix) + mede (from medu, which became modern mederu, "to like, to adore") + itashi ("extremely", possibly related to modern itai, to hurt).
Bonus link: "Cool, I get drunk!"
Azuma:
I would only add that the Kansai consonant dropping phenomenon didn't just bring these few words into Standard Japanese, it created a whole politeness register for potentially all adjective forms that usually only appears now in arigatou, omedetou, and a few others. It's the only way to get a "gozaimasu" level out of adjectives. "ureshuu gozaimasu"(which I've heard in a number of speeches), "wakou gozaimasu", etc.
Here's a page I found: http://home.alc.co.jp/db/owa/jpn_npa?stage=2&sn=170.