Be ready to experiment with keys a lot too, in addition to scales. I'll give an example so you can see where I'm coming from. I've noticed that many of my favorite Radiohead songs step outside of a single key into multiple keys throughout the song. Take Radiohead's Sulk from The Bends album, for instance. This entire part is a big section of the song but it doesn't fit into any single key. It goes:
D D(octave) Db(half-step down) A
D D(octave) Db(half-step down) A
C C(octave) B(half-step down) G
D D(octave) Db(half-step down) A
Music theory says that the 'D' riff is either in the key of D major or A major (because they're the only ones that have D and Db in them) but that the 'C' riff couldn't possibly be in either D major or A major (because of the C). So my way of looking at it says Radiohead changes keys here and the theory says it goes to either C major or G major (because they're the only ones which have B and C in them). You now have 4 keys to choose from for soloing/comping over this and can start experimenting with what the key of A major sounds like over the 'D' riff (hint - start on the D not the A), what the key of D major sounds like over the 'D' riff, etc. IMO, the theory helps out a lot and can help move your solos in the right direction just by giving you new keys (and more notes) to use. If you can look at a chord progression and tell which key (or keys) it is in then you've made a big step in making theory work for you and your solos. Eventually the right sounds should come out naturally after playing around with the right keys and extra notes long enough (that's my theory anyhow

).
If you want to look more into key changes so you can practice finding them in other songs or soloing across multiple keys, there are more changes in Radiohead's Sulk, in Beck's Guess I'm Doing Fine from the Sea Change album and in David Bowie's Space Oddity.
One thing to add, as everyone has pointed out, is that major and natural minor (a.k.a. Ionian and Aeolian) are very good scales to focus on. As it turns out, you can use multiple scales while staying in just one key. As an example, the C major scale has the same notes as the A minor scale. Both are in the key of C major, but they sound very different. Experiment with playing both scales back to back in a solo and you'll see what I mean. You can also stick with just one scale (i.e. major) in your solos and change keys once in a while to have some fun (if it jives with what the rhythm, bass, and vocals are doing, of course).
Cheers,
Shaun