What is "Key"?

In simplified terms, the "key" of a song determines the scale used.
The notes in any major scale can be derived from this pattern:

W W H W W W H

W: whole step (tone)
H: half step (semitone)

For example:
"Key: G" indicates that the notes in the song follows a general adherance to the G major scale i.e.

Notes in the G major scale:

GABCDEF#G
WWHWWWH