Survival in the wild, and pattern-matching
Why do we have ears in the first place? It's for survival. The ears (and the rest of the auditory system) are supposed to tell us what's going on in the world. Rockin' Cowboy mentioned the Basilar Membrane, which is able to do a real-time spectral analysis of the sound. However, a full spectrogram would be a lot of information to process and we're busy doing other stuff (seeing, eating, moving). So the auditory system is a big pattern-matching machine - it does some clever stuff to match the different frequencies it's receiving to each other and try to divine some information about 'things that are happening'.
The harmonic series
Sound is vibration, and in nature, if something is vibrating at a frequency, it will also tend be vibrating at multiples of that frequency. So one of the things the ear does is look for frequencies that are multiples of each other, and if it finds them, it tells us that this is 'one sound' - one 'thing' in the world that is vibrating. So if the ear hears vibrations at 1000Hz, 2000Hz, 3000Hz... all at the same time, it sees that as one 'note'. And as you say, it's not particularly surprising or special - it's just the ear hearing what it's expecting to.
Showtime!
What happens, though, if we play two notes that are related in frequency? Say, one at 1000Hz (with harmonics at 1000Hz, 2000Hz, 3000Hz...) and another at 1500Hz (with harmonics at 1500Hz, 3000Hz, 4500Hz...)? All of a sudden the ear's pattern-matching mechanism goes a little bit wild. Wow, what's happening? It's two sounds (sets of related harmonics), but they also kind of merge into one (as the frequencies of the harmonics of both are closely related to each other). It's a bit like the aural equivalent of an optical illusion.
If we're playing these notes at the same time, then we're talking about harmony rather than melody. But as we have memory and the ability to 'pattern-match' things that happen across time, similar principles apply even when we are talking about two notes that happen one after another.
Scales
So, if we want to come up with interesting combinations of notes, why not come up with a set of notes that have interesting frequency relationships, so we can choose to play them one after another to make up a melody? Great idea - and that's what a scale is.
Try having a play on http://labs.dinahmoe.com/plink/. Can you see how it pretty much always sounds 'good'? That's because it's using a pentatonic scale that has simple frequency relationships between all the notes (http://www.phy.mtu.edu/~suits/pentatonic.html). It's called 'pentatonic' because there are 5 notes to each octave.
A very popular scale in western music is the Diatonic scale. This allows for many simple frequency relationship between notes, but also some that are not so nice. This gives rise to the idea of 'tension' and 'resolution' - the way that you can create interesting melodies by mixing nice consonant intervals (frequency gaps with simple ratio) with more harsh, dissonant ones.
Another scale that would be worth reading about if you are interested is the 12-tone even tempered scale - another western scale that is a clever way of squashing a few more notes into the diatonic scale such that you get 12 evenly-spaced notes in an octave.
And there are many other scales in use around the world (some of them seem designed to work with instruments that don't have harmonics that are integer multiples of a base-or fundamental- frequency : the Gamelan and its associated scales is an example of this.)
And there's more
Of course our ears can match patterns other than frequency ratios. We can perceive rhythms - ratios in time between sounds. Again, we perceive regular rhythms in a special way - you could again consider this might go back to nature as they are found in things like walking, breathing, dripping, chewing, heartbeats, many animal songs, and so on. But the brain will even match patterns that aren't 'natural' (think of letters, and words, for example) and rhythms are just that: patterns in time.
Also, remember the way that the ear likes to try to correspond frequencies with a 'base' frequency at the bottom of a harmonic series? It likes to do that with whole songs as well, so there is a 'root' note that it's satisfying for the melody to return to.
And the brain will find satisfaction in recognising higher-level patterns, too. Think of a song like London's Burning. There are two groups of two notes followed by two higher notes, and then two of the same note, then a stepwise downward pattern occurs twice as the melody goes back down to the root. And there is melodic correspondence with the rhythm - the first syllable of 'burning' is the strong beat of the rhythm, and it's no coincidence that that's also the root note.
Music doesn't exist in a vacuum - we experience it while we are doing and seeing other things, and we may tend to enjoy melodies that we associate with other good times or good things. We may love our national anthem despite it perhaps not being the kind of tune we usually like, for example. Happy Birthday is another example of a melody that we associate with good times!
And there's plenty I still haven't considered here - lyrics, the timbre of the sound that's playing the melody, how the melody relates to the harmony...
So, does any of this help us write good tunes?
Even if we consider melodies to be only sets of pitch and rhythmic relationships, they're complicated. 3 notes have 3 relationships between them. 4 notes have 6 relationships. 10 notes have 55 relationships (these are triangular numbers, by the way : http://en.wikipedia.org/wiki/Triangular_number). And this is before we start analysing the relationships between groups of notes.
Also - people get bored. The nursery rhyme-like tunes we loved when we were small may not seem so exciting now. As we grow up, we get bored of nice relationships between notes - Some of us want to hear something new - so we all go off and listen to jazz where they use all the notes at the same time, or classical music that changes key every half a second, or rock music with the sound so distorted that it generates a whole load of other frequencies not related to the original notes...
And of course, people like different melodies (and harmonies) for reasons that are as hard to explain as why they like different foods, sports, books.... There many, possibilities in a scale system like 12-tone equal temperament, and within those, you'll find, for every person, many things that annoy them, many things that bore them, and many things that excite them. Different styles of music tend to use melodies (and harmonies) with different characteristics, so that melodies in heavy metal songs are not the same as boy-band songs. That group of friends hanging around outside a concert may just be together because they happen to like the same melodies. And do they like them because they have learned to like them, or because of something to do with their basic brain chemistry? Who knows?