I don't know if I can explain this very good, but I will try. I am kind of behind on theory because I didn't pay much attention in class.
First you need to learn how to build the scales in those keys and know how a major key is different than a minor key not just in sound but in structure.
If the melody is in C major it will usually start on C in the beginning and it will more than likely end in C at the end of the piece or phrase. In A minor it will likely begin on A or go back to A often as it's the tonal center of the key. Both C and A minor have no signs in their key signature, so if you are determining the key of a whole piece and it has no signs then look at the beginning and look at the end. Does it end with A or C, etc... The problem is, it's not always the root note that it starts or ends on, you'd need to learn harmony and how to build the triads.
Then you need to know what sharps or flats the most used keys have.
When you look at a particular passage of music, check the accidentals that will occur, new flats or sharps, naturals, etc and figure out which key they belong to. New sharps or flats don't always mean a new key. Minor keys are a good example of that. We often have C# in D minor (the 7th degree in minor is often raised, if it is a key with flats it will be a "natural" which would also raise the note).
Here is what you can do. Look for the most important notes in a bar and try to use chords that have notes notes in them. You will be able to judge if they are right or not. Note of longer duration for example might be more important than short duration notes that might just be leading the melody to somewhere else in between but the chord you use before them will sound good together with them as well.
You don't need to put a chord to every single note. Also look at the shape of the notes in the one bar, put them together horizontally in your mind, do they make up a chord that you might recognize? This is a giveaway for the key it's in currently and it happens often.
I will give you an example with a piece I am playing these days.
This is Bach's G minor sinfonia. It's a polyphonic piece (meaning all voices are of equal importance and it's not simple melody and accompaniment). Look at the shape of the notes in that measure (left hand), put them together. The first 5 notes played together spell out the D minor chord. We are in D minor.