I know that C major and A natural minor have the same key signature. Are they considered different keys though? Is modulating from one to the other considered a key change?
Yes it is a key change because functionally where the harmony is going is different. A key in general tells you two pieces of information: a general idea of harmony and the note you will sound at rest on known as the tonic. Even though they share the same notes, both the general harmony and and the tonic are much different.
To be in C major and to be in A minor look very different harmonically. In C major you'll typically use G or G7 to get back to C. When you factor in minor key harmony, which utilize the leading tone, in A minor you're most likely using E or E7 to get back to A. They are two distinct concepts.
I would add to the previous answer that when one writes in a minor key the Harmonic and/or melodic minor scales are used to create resolution from the relative V7 to i (the vi of the relative major) by creating a leading tone in the minor key. With these accidentals in place you really cannot say you are in the relative major.
You don't need this device to hear the minor key. To "hear" minor you would need melodic lines and progressions structured in such a way that focuses attention on the minor scale. You could write a melody that focuses on the 6 and 9 of the I chord (example, A and D of C major) and that will not sound minor nor will it make sense to say you are playing in A minor. But adding G#, and possibly F# in the melody line to move into A, or having progression or vamp like A- --> D-, etc will definitely sound minor.
It's a combination of these factors that distinguishes "key".