I've heard guitarists tell me "Even if I've never heard the song, if I know it's key, then I can usually play through it O.K"
There's a term for it, I know. Anyways, I understand the concept of keys, intervals, etc. But, what exactly is going through the minds of these guitarists when they're playing that allows them to do this?

A few notions that come to mind are:
1. 95% of songs start on the I chord of the key. So, you can bet if it's in E minor, it will start with an Em chord.

2. There are conventional chord progressions for each given music genre. So, you can bet that if it's blues, there will be a IV and V chord in there somewhere after the I.

I guess my question is, with my knowledge of music theory, and good memory of note location on the fretboard. What exactly should I be thinking after the guitarist yells out "We're in A" and it's time to start playing a song I've never heard before.

For blues there are standard progressions. For rock and country most songs will also use I IV V, not necessarily in that order. If the guitar player is being nice, he will give you a leading tone into the chord.

Then it is just a matter of listening. Bridges and key changes are the hardest.

It's not a matter of "thinking" it's (as SEEN'EM points out) it's a matter of LISTENING. Or more accurately HEARING WITH CLARITY. The term you may be looking for is RELATIVE PITCH. But more accurately the ability you are talking about is being able to hear chord quality and function with enough clarity that you know what you are hearing. And, since it doesn't really to do you much good to do so after the last set, you need to be able to do this while you're actually playing the tune.
SO it's gonna be something like
1. hear root movement - somebody yells "We're in A" and the very next thing you hear after the first chord is that the root moves from A up a minor 3rd (or to C)

2. hear the triad - the first chord was built off a major triad and when it went to C, you hear a minor triad.

3. Hear full chord quality - you hear that the first chord was actually a dominant chord (A7) and that the second chord is a minor seventh chord (C-7)

4. Hear chord function - this is a little harder without at least knowing the tune well enough that you can sing the melody. Is that change from A to C an actual shift in function or was the first chord just a revoicing/inversion of the second one? Does the tune actually follow functional patterns of resolution/voice leading etc. or is it more a "modal" world jumping from chord to chord without any real functionality?


I'm not sure what you mean when you say "good memory of note location on the fretboard". What kind of ear training work are you doing?

Another thing to add is when you've learnt so many tunes in all styles they tend to stick to famous progressions so if you use the roman numerial system or simply using your ear or both you'd be able to antisipate the next chord but sadly you have to learn many tunes as well as learning your intervals and hearing chords with there progressions but you will be rewarded if you put the time in it.
Also having a good memory helps too cause chances are you'll come across the same progression but a different artist will sing on it.