Patrx2 and Dom's answers are both very good. To add to them:
Usually I determine the root (C or A) taking into account clues like:
The happy or sad feel of it all
I think Patrx said it quite well, I would add that minor sounds darker to most people than major, but adding meaning and emotional content to the sound is the function of the artist, it is not dictated by the chords. Darker often gets associated with sadder, but to quote Van Gough "I often think the colors of the night are more vibrant and alive than those of the day."
The first chord (C or Am)
Is as mentioned is not a reliable indicator. However, in popular music the root of last chord will almost always be the root of the song. The chord quality may have been substituted (e.g. its not uncommon to write songs in minor keys and then substitute all the chords with major chords on built on the same root.)
Stereotypical tensions like G7-C or E7-Am
The tension and release provided by V7 to I (and the accepted substitutions for it e.g. tritone, common tone, etc.) is more than just a stereotype, its part of the structure of western music. Its just an inescapable part of how we are culturally conditioned to hear music. Regardless of how modal, atonal, avant-garde, or experimental a piece may be, it still exists in a world where it is specifically playing against the listeners expectation of a satisfying old school authentic cadence.
V7 to I is less of an indication that a key has been established, its simply how a key is established, when it is placed on strong beats in important parts of the songs overall form.
To use your example:
As I've no doubt quoted before - look at Fly Me To the Moon. C or Am? Who knows? Who cares?!!
I wish I had the recording, but assuming the chords on ultimate guitar are correct http://tabs.ultimate-guitar.com/f/frank_sinatra/fly_me_to_the_moon_ver5_crd.htm I would say the song is clearly in A minor. It ends on A-7 (starts on it as well), and is constantly going E7 to A-7. Of course those chords could be 100% wrong, I'm basing my call here on that specific link.
I feel your pain though, I distinctly remember that what the hell is going on here? feeling trying to figure out *God Only Knows" off the Pet Sounds CD.
Edit:
In Phil Smith's answer he points out that the last chord in Fly Me To the Moon is actually a C not an A-7 as it is transcribed on the link I referenced earlier. In which case I will stick to my theory and say if the last chord is a C, the song is in fact in C not in A minor. If the chords on the linked page were correct, the song would be in A minor, but apparently they are not correct.