The key of a song is NOT determined by the notes being played. That is the purpose of the key signature which is completely different. If that were the case then there would be no need to make the distinction between C major and A minor since they both contain the same notes. If you want to learn how to figure out the key of a song then I suggest you study diatonic harmony, modal harmony, and learn the roman numerals for chords. Once you understand that apply the knowledge to your ears.
So then what is the difference between the two keys? C Major and A Minor?
The tonal center. Even though they contain the same notes they are both completely different. A song in C Major revolves around C Major and a song in A Minor revolves around A minor.
The key of a song is determined by a tonal center.
What is a tonal center?
The tonal center is a tone/chord the music seems to revolve around. In traditional songwriting the song is expected to resolve to the tonal center.
If the song revolves around an A minor chord then its in the key of A minor. Likewise if the song revolves around a D minor chord then the key is in D minor. The key signature however is only adjusted according to note clarity.
However according to functional harmony an A minor chord leaves the possibility of three different tonal centers/keys. How is that possible?
Key Signature of C (Cmaj Dm Em Fmaj Gmaj Am Bdim) According to functional harmony there are 3 minor chords in a key signature. In this case Dm Em and Am
The chord Am could also be found in the key signature of G major and F major.
(GMaj Am Bm Cmaj Dmaj Em F#dim)
(FMaj Gm Am Bbmaj Cmaj Dm Edim)
For the sake of clarity we begin to use modal harmony.
Play the C maj scale but instead start on D and you get D E F G A B C D. This is the Dorian mode.
Starting on E is Phyrgian
Starting on F is Lydian
Starting on G is Mixolydian
Starting on A is Aeolian/Minor
Starting on B is Locrian
Apply this to modal harmony and you get for example starting on D
Dm - Em - Fmaj - Gmaj - Am - Bdim - Cmaj.
You should get the picture.
So how is this gonna help train your ears to recognize keys?
If you hear two major chords followed by a whole step then you know that you are on the IV chord or the V chord. We know that the IV & V chord have to be major so if any of those are used as the tonal center then the key would automatically be major or if you wanted to show its relative key signature you would say Lydian or Mixolydian.
In another case if the tonal center of the song revolved around the IV chord then the key of your song would be F major but since F major also implies three key signatures it would be wiser to say F Lydian which shows that its relative to the key signature of C major.
If you found that hard to follow then I suggest you get started studying those topics I gave you at the beginning of the thread. As a hint, you can usually tell the key/tonal center by listening to the bass of a song.