This answer is separate from my other one because it attempts give a more basic answer, to meet the bounty request.
What exactly does it mean if for example a song is written in C Major?
Does it mean the song's notes cannot contain any sharps or flats?
In the most basic sense, yes, this is what it means. The melody and the chords will be constructed only from notes in C major scale -- and those are the white notes on a piano; no sharps or flats.
Does it mean the song can only have chords from ABCDEFG but use the major chords of those scales which could mean sharps and flats?
No. The chords will also only contain notes from the C major scale.
So the major and minor chords you have available are: C, Dm, Em, F, G, Am, Bm. These are the chords you get when you start on the note denoted in the chord name (C, D, ...), and play the third and fifth notes from there within the C major scale.
Now, if you see a piece that has no sharps or flats, that's not enough to tell you whether it's in C major or A minor -- since both of those are played with no sharps or flats. To decide which it is, you must work out what the tonal "centre" of the melody is. This is a matter of feel, so it's not possible give a strict definition. But it's often (but not always) the first note of the melody; even more often (but not always) the final note of the melody; and it's a note that will often end phrases within the melody.
So, if a tune has no sharps or flats, and seems to have a "home" at C, it's in C major. If it seems to have a "home" at A, it's A minor.
If its "home" seems to be a note other than A or C, then the tune is in a more obscure (in Western music) "mode"; I suggest avoiding that topic until you are comfortable with the basics.
The reason some of the other answers have been less clear, is that with more advanced pieces, things get more complex. If you sneak (for example) one Bb into a tune that's otherwise in C major, it's probably still C major. That's why we have to use words like "mostly".