The subject says it all. As far as I know, C major has all the same notes as A minor, so what’s the difference?
A minor is known as a “mode” of the C natural scale. There’s no difference. We just use the words to distinguish when it’s used (i.e. different chords would be played over the scale depending on the mode)
The notes are all the same but the relative intervals between where you start and where you end up are different in a few key places. If you play up from a C to a G and back down again, the jump from the 2nd note to the 3rd one is a whole step; if you go from an A to an E and back, the jump is a half step. Therefore, the chord based on the note you started is a major chord in C, and a minor one in a. This means that, in the broadest possible terms, something played in C is going to be happy, and something played in a is going to be sad or melancholy. There are other intervalic difference, but that’s the gist of it.
The natural minor is also known as the Aeolian Mode, FWIW. There are seven modes total(derived from the seven notes in the major (Ionian) scale). Since each mode has a different “base” note, the chords derived for each mode will be different.
For more info on modes check here:
http://en.wikipedia.org/wiki/Musical_mode#Modern_modes
There’s no difference in that the keys used in C Major (Ionian) are the same as A Aeolian. (all the white keys on a piano).
But the keys emphasized are different. For something to be in the key of A, A is sort of the baseline that everything revolves around. So, when you play a D, listeners are aware that this is the fourth. When you’re playing in the key of C and you play a D, listeners hear this as a second.
When you play in the key of A, you’ll tend to have more A’s, and more A’s on beats. And more E’s (a fifth above). When you play in C, you’ll expect more C’s and G’s.
I’m talking in huge generalities here, but that’s the gist of it: the keys are the same, but the notes emphasized are different.
The chord progressions and implied harmonies will be different in C major and A minor. Like Bill said, in C major, everything revolves around the C chord. Most tunes will end on a C major chord. Most melodies will also end on the C note.
In A minor, your A minor chord is the foundation, or tonic, chord. Most progressions will resolve to A minor. Most melodies will end on it.
It’s a bit more difficult to explain in writing than in front of a piano where I can play you examples.
Also, the harmonies will be different. In A minor, you will get chords such as E7 (E G# B D) that usually don’t appear in C major. You may also find D7 (D F# A C) in A minor, that you normally wouldn’t in C major.
While the two scales have the same exact notes, the melodic and harmonic expectiations of them are very different.
I have only one thing to add to what has been said so far: numbers. Bill H touched upon them but since “fourth” can be both a chord position and a two-note interval, I’m going to rephrase it this way.
One way of looking at a particular key is to number it. In the key of C, begin at C and make a triad (C - E - G) and call it Roman numeral I. Continue up the scale through D, E, F, etc., until you are back to C. Your I is the tonic, or base key, that pulykamell describes.
The chord five up from this is known as the dominant, or Roman numeral V. It is the dominant chord which naturally tends to lead back to the tonic. Four up from the tonic, or five down, depending on how you look at it, is the subdominant, or IV. I, IV and V are the most common sounds in any given composition (as a general rule).
Chord theory can be broken down into the numbering of progressions in just this way, because the numbering is independent of key. I could merely memorize that a particular popular song went I - IV - I - IV - I - IV - V and apply this information to any major key!*
In the key of C, the numbering always begins with I on C, ii - D, iii - E, IV - F, V - G, and so on. C is the tonic, F is the subdominant, and G is the dominant.
You’ll notice that ii and iii are in lower case. That is because in C – and in any other major key – these constructions are naturally minor chords.
Now to examine A minor. It begins on the tonic, yes, but now the progression is i - Am, ii° - B diminished, III - C, iv - Dm, v - Em. A minor is the tonic, D minor is the subdominant and E minor is the subdominant.
So C and A minor have the same key signature, but in C major, the progression goes I - IV - V (all happy major chords) and in A minor it would have to change to i - iv - v (all melancholy minor chords**).
*I could apply it to minor keys as well but it takes some additional musical gymnastics.
**Yes, yes, I could get into using an E major instead of an E minor dominant in the key of A minor, but I went too far already. 
I was going to comment and that, but you caught yourself. Generally the V in both major and minor chord progressions is major, hence my note about the E7 chord appearing in A minor.
Dare we go into natural minor v. harmonic minor v. meloid minor?
Ahem…that should be “melodic” not “meloid” minor.
Okay, but you get to explain the augmented second. 
You would DO THAT?
No, but here’s some more information about keys for gratis and nothin’ since you asked.
Your original post noted that the keys of C major and A minor were all the same notes, which is true. Most people first become aware of this because the two keys use the same key signature: no sharps or flats. But many people ask, what is a key signature, and why do C major and A minor use the same one?
Look at this badly-rendered picture of a piano keyboard:
Db Eb Gb Ab Bb
C# D# F# G# A#
CC DD EE FF GG AA BB CC
CC DD EE FF GG AA BB CC
Consider the scale C D E F G A B C. In between C and D is the note C#, making this interval a whole step. In between E and F there is no note, making this interval a half step.
Major keys can be described by the following intervals: 1 1 ½ 1 1 1 ½.
If you try to construct the key of D you will find that following the above pattern requires you to play some black keys: F# and C# particularly. The progression goes D E F# G A B C# D, so the key signature consists of two sharps, one on F and one on C.
Therefore, rather than clutter the staff with sharps strewn higgledy-piggledy, musicians just throw the sharps into a reminder at the start of the song, as in, “Don’t forget, Maestro, every time you see F, you play F sharp unless we say so.”
If you try to construct the A minor scale — A B C D E F G A — you will find to no surprise that no black keys are needed. You will also discover that it does not go 1 1 ½ 1 1 1 ½. Minor keys go 1 ½ 1 1 ½ 1 1.
So that, dear reader, is how the elephant got his snout. Now somebody can segue into natural and harmonic minors if they’re so inclined and if the OP is still awake.
I always wondered about stuff like this; is the sensation caused by the key “genetic” or “cultural”. Would islanders raised away from the western world consider music in “C major” to be happy, and “A minor” to be sad?
And while all these musically astute people are in this thread, may I ask a question I posed months ago but which didn’t seem to get a satisfactory answer:
Why does a composer picks a certain key to write an opus in?
I know it often changes from movement to movement, sometimes within a movement. But what is there about a particular key that ‘compels’ the composer to select it as the preominant one? Why, for example, did Grieg write his breathtaking Piano Concerto in A Minor, rather than G Flat, or… you pick a key?
Did Mozart, Beethoven, Bach and the others each have a favorite key? If yes, why was that key so appealing?
I know a few musical prodigies (no composers, though) who insist that using different scales does make a difference, and they like, for example, G major more than E major.
Quick answer (I’m running off to work):
-
Some people “feel” differences between C major, D flat major, D major, etc… I do to some extent, but I don’t have perfect pitch so I wonder if some of it is psychological. There really isn’t much difference in modern tuning (equal temperament) between the keys. However, this mostly applies to piano and instruments with fixed tuning. Strings, brass, etc., have the ability to play outside equal temperament pretty easily.
-
Back in the day (pre-20th century), most pianos were not equal tempered, but rather well-tempered. This meant that there really was a distinct difference between the various keys. C major sounded different from C# major. The tuning was stable enough that all 12 keys could be played, while all of them retained individual character.
-
The instrument itself. A standard-tuned guitar plays easiest in E, A, D, and G. These keys also allow plenty open strings to ring, giving the chords a fuller and different timbre than if trying to play a standard uncapoed guitar in G flat. Same with all instruments. There are just some keys which are better suited for songs than others. On the piano or organ, F is a great key for blues. The keys (F A-flat B-flat B C E-flat) just fall naturally into the shape of your hand and allow you to play blazingly fast runs which would not be possible, or at least as easy, as in other keys.
-
Vocal range. Anytime you’re composing with vocals, you have to keep in mind the range of the people you expect to sing it.
Thank you very much, puykamell, for a most informative reply. (Feel free to elaborate when you get back from work. 
)
Now, maybe someone will answer BwanaBob’s question (post 13). Hope so, anyway. I’d like to hear it, too.
FWIW, I once read about a man from India who attended a western concert for the first time (here in the U.S. I think).
Afterwards he remarked that he especially liked the music the orchestra played before the conductor took the podium.
I always thought that was endearing, somehow.
Not necessarily. In Byzantine church music, there are four modes, one corresponding to Western major, one to Western minor, and two that are variations of each other and don’t correspond to Western modes at all, and use intervals that are somewhere between a half step and a whole step, or slightly more than a whole step.
The mode corresponding to the major scale is felt to be unadorned, masculine, and aggressive – not necessarily happy, but strong and energetic.
The mode corresponding to the minor scale is spiritual, joyful, and radiant – the music of Easter is mostly in this mode, so it could be considered “happy”.
The latter modes are feminine, sweet, and mournful – the “sad” modes.
I believe it to be cultural. I don’t have any direct evidence for that except that some music from countries that use quarter-tones and other harmonics not found in western music can sound, to me, really freakin’ weird, but people from those cultures think it’s standard fare.