The answer is complex due to the way the GPS system operates, so I'm going to simplify a number of things so you understand the principle, but if you are interested in how it's really implemented you'll need to go find a good GPS reference. In other words, what's written below is meant to give you an idea of how it works, but is technically wrong in some ways. The below is not correct enough to implement your own GPS software.
All the satellites transmit on essentially the same frequency. They are technically walking all over each others' signals.
So how does the GPS receiver deal with this?
First, each satellite transmits a different message every mS. The message is 1024 bits long, and is generated by a pseudo random number generator.
The GPS receiver receives the entire spectrum of all the transmitters, then it performs a process called correlation - it generates the specific sequence of one of the satellites, multiplies it by the signal input, and if its signal matches a satellite's signal exactly then the correlator has found one satellite. The mixing essentially pulls the satellite's signal out of the noise, and verified that 1) we have the right sequence and 2) we have the right timing.
However, if it hasn't found a match, it has to shift its signal by one bit and try again, until it's gone through all 1023 bit periods and hasn't found a satellite. Then it moves on to trying to detect a different satellite at a different period.
Due to the time shifting (1023 bits, 1,000 transmissions per second), in theory it can completely search a code in one second to find (or determine there's nothing) at a particular code.
Due to the code shifting (there are currently 32 different PRN codes, one each for each satellite) it can therefore take 30+ seconds to search each satellite.
Further, doppler shift due to the speed of the satellite relative to your ground speed, means that the timebase could be shifted by as much as +/- 10kHz, therefore requiring searching about 40 different frequency shifts for a correlator before it can give up on a particular PRN and timing.
What this means
This leaves us with a possible worst case scenario (one satellite in the air, and we try everything but the exact match first) of a time to first fix off a cold start (ie, no information about the time or location of the receiver, or location of the satellites) of 32 seconds, assuming we don't make any assumptions, or perform any clever tricks, the received signal is good, etc.
However, if you have two correlators, you've just halved that time because you can search for two satellites at once. Get 12 correlators on the job and it takes less than a few seconds. Get a million correlators and in theory it can take a few milliseconds.
Each correlator is called a "channel" for the sake of marketing. It's not wholly wrong - in a sense, the correlator is demodulating one particular coded frequency at a time, which is essentially what a radio receiver does when you switch channels.
There are a lot of assumptions a GPS receiver can make, though, that simplify the problem space such that a generic 12 channel receiver can get a fix, in the worst case, in about 1-3 minutes.
While you can get a 3D fix with a 4 channel GPS, when you lose a GPS signal (goes beyond the horizon, or you go under a bridge, etc) then you lose 3D fix and go to 2D fix with three satellites while one of your channels goes back into correlation mode.
Now your receiver starts to downloaded the ephemeris and almanac, which allows the receiver to very intelligently search for signals. After 12 minutes or so it knows exactly which satellites should be in view.
So the search goes pretty quickly because you know the position and code for each satellite, but you still only have a 2D fix until you actually find a new satellite.
If you have a 12 channel receiver, though, you can use 4 of the strongest channels to provide your fix, a few channels to lock onto backup satellites so it can switch the calculations to them if needed, and several channels to keep searching for satellites the receiver should be able to see. In this way you never lose the full 3D fix.
Since you can only see up to 12 satellites, why would you need more than 12 channels?
There are 24 or so GPS satellites operating at any given time, which means that on one point on the earth you can really only see half of them.
But remember - you can only search for one satellite per correlator, so the primary reason to increase correlators past twelve is to improve the time to first fix, and the main reason to improve that is for power consumption.
If your GPS chipset has to be powered all the time, it's a 100mW power drain all the time. If, however, you only need to turn it on once per second for only 10mS each time, then you just cut your power consumption down to 1mW. This means your cell phone, location beacon, etc can operate for two orders of magnitude longer time on the same set of batteries while still maintaining a full real time fix on their location.
Further, with millions of correlators, one can do more exact searches which can help reduce the effects of radio reflections in urban canyons (tall buildings in big cities used to foul up GPS receivers with fewer correlators).
Lastly, while only 4 satellites are needed to get a 3D fix, good receivers use more satellites in its position algorithm to get a more accurate fix. So only a 4 channel receiver is required, but a 12 channel receiver can get more accuracy.
So the millions of correlators:
- Speeds up satellite acquisition
- Reduces power consumption
- Reduces likelihood of losing a 3D fix even in urban canyons
- Provide better sensitivity, allowing fixes in dense forests, and even in some tunnels
- Provides better positioning accuracy
Thanks to borzakk for some corrections.
Adafruit Ultimate GPS is in no way representative of all GPS receivers out there. Many good receivers have more channels than that; 256 is common in high-end devices. Note that 256 is not divisible by 3, so the factor of 3 you're seeing is a red herring.
Also, you rarely get a signal from 22 satellites, and it's not necessary to have a fix. Having a signal from 7-10 satellites is quite common in real-world conditions.