The key is given by the number of sharps and/or flats.
A song in the Key of "C" major, or its relative minor ( A minor) presents no sharps and flats. So you can use a "C" major scale or an "A" minor scale for the solo part.
As for the chords; you have to harmonize the scale. That means building chords based in the scale only.
When you harmonize the "C" major scale, none of your chords contein sharps or flats. These are the chords for the harmonized "C" major scale:
C major
D minor
E minor
F major
G major
A minor
B diminished.

Note that if you play an "E" major, you would use a G# as part of the chord; and G# is not part of the "C" major scale, in consecuense your solo and chord progression wont match. Therefore the E minor chord is to be played in your chord progression.