A sequence of notes, like a sequence of numbers, can be related, or unrelated. As far as numbers go, the series of numbers 1,2,3,4,5,6,7 etc. have a specific relationship to one another and we can easily recognize this pattern. Likewise the numbers 2,4,6,8 have a certain identifiable relationship as do the numbers 7,14,21,28,35. There can be a sense of order in the relationships - regardless of what order you place the numbers - or a sense of order based on the order of the numbers which form a predictable pattern.
If we construct a string of random numbers such as 3,4, 7, 12,19,22,37,23,72,86,43 - we may not see a relationship or pattern that is identifiable or predictable.
Music is very similar to math in that it deals with sound frequencies that can be measured in terms of a certain number of oscillations or cycles per second. A string vibrating a given number of times per second or millisecond - will create a specific sound through the process of converting the vibrations to sound waves which in turn will translate into sound we hear via corresponding vibrations of the basilar membrane in our inner ear.
A string vibrating at a different rate of speed will result in a different note. If there is a simple mathematical relationship between the two frequencies, we will detect a pattern or sense that the two notes somehow belong together or go together or have an identifiable and detectable relationship to one another.
For example if the ratio between the frequency of two notes is 2 to 1 or two times as fast (two wave peaks for one note to every one wave peak of the other) - this 2:1 frequency is known as an octave. It's the same note - exactly one octave higher (vibrating exactly twice as fast = octave higher or half as fast = octave lower). That is a simple mathematical relationship.
Between a note and the octave (doubling or halving of frequency) are many other possible notes with varying ratios. In Western music, we divide an octave into 7 possible notes using mathematical logic and simple integer ratios.
The relationship between the mathematical characteristics of the soundprint (frequency of crest of sound waves plotted on a graph) of the notes that are in a given key (7 possible notes per key in Western music) all have a mathematically definable relationship to one another with the intervals between each note of the key being dependent on the type key (major, harmonic minor, natural minor, melodic minor etc.).
If not for the equal temperament tuning system (another topic altogether) each major key will contain a note that has a frequency relationship to the tonic note (aka root note - C in the key of C, D in the key of D etc.) of 3:2 which makes a perfect fifth. The perfect fifth is a stable harmonious interval between notes and will be found in most keys - even in equal temperament. A pitch ratio of 4:3 makes a perfect fourth which is another simple interval that sounds stable and pleasing.
The seven divisions of an octave that make up the notes for a given key are derived by application of mathematical principals and formulas. In real life, adjustments have been made with a system of tuning called "12 tone equal temperament" that deviate slightly from the perfect mathematical formulas - to allow for the use of keyboards that have only 88 keys and can transpose music to any key.
For the most part, the resulting pitch ratios determine the notes that form a given key. One way to see how these ratios can be used to construct a key is by application of the perfect fifth (the most stable interval besides the unison 1:1 and octave 2:1) to a series of notes to determine which notes belong in a given key.
For example to determine the notes that will fit in the key of C major you start with the root note C and take the first perfect fifth inversion (work backward 7 steps in descending order) and you arrive at the note of F. Another way to look at this is to determine which note the root note is the perfect fifth of which C is the note that is a perfect fifth above F. A perfect 5th interval in Western music is always the starting note and the note that is exactly 7 semi tones above the starting note (3:2 pitch ratio) So if you start on F and go up a fifth - you land on C. Up a fifth from C gives you G. Up a fifth from G gives you D, up a fifth from D gives you A, up a fifth from A gives you E and up a fifth from E gives you B.
F—C—G—D—A—E—B - each note a perfect fifth higher than the preceding note and the end result of counting 7 steps each time gives you all of the notes contained in the key of C major. The same process works for the key of D, D# E, F, F# G etc.
The point being, there is a mathematical formula that can be applied to determine the notes in a given key. This mathematical formula will insure that the pitch ratios between all the notes of a given key (equal temperament notwithstanding) are related by the fact that they are multiples or divisors of one another and thus the sound waves will eventually coincide (every so many peaks) and blend. Notes not in the key will not have their waves coincide and they will clash - and not seem to go together.
Certain frequencies of sound or vibration patterns of the sound waves, imply other frequencies to our brain that are mathematically divisible by the primary fundamental frequency. So the brain implies or infers certain notes that will go with the fundamental note based on this mathematical inference phenomena that occurs in our auditory processing center. So we can form melodies in our head and the notes we "hear" in our head will naturally be in the same key. The other notes are "implied" by this mathematical processing.
Sound waves that don't overlap or cannot be mathematically derived by a multiple of or divisor of one another, create an uncomfortable sensation to our ears known as beating. The sound waves clash with one another instead of blending together. Notes not in the same key will be detectable as not belonging together by our brain because they won't fit together via the implied inference to one another in the subliminal overtones.
That is why certain notes seem to belong together whether playing a scale which is a derivative of a particular key and spans an octave - or playing a melody within a particular key. The very sophisticated and still not completely understood computer in the auditory processing center of our brains knows which notes belong together because it can do the math subliminally - faster than our calculators.
EDIT: We instinctively know which notes seem to go together. Our brains gravitate towards related notes and melodic patterns naturally. To some extent our musical preferences can develop a cultural bias based on what we regularly hear from childhood on - and the emotions that are associated with particular types of music we are exposed to. But we are born with a certain musical sense that in the absence of cultural influence would evolve as explained by the mathematical relationships between notes described above. Music theory is nothing more than an attempt to logically or scientifically explain why we instinctively know what notes go together - so we can apply said theory to help us create music that is pleasing to our ears.
The first time a cave man (or woman) accidentally stumbled upon a perfect fifth while blowing through hollow sticks of varying lengths, he/she became the worlds first "rock star". The other cave people could not explain why the sequence of notes sounded so pleasing together, because music theory had not yet been developed. But they did know it sounded good.