Primer: Intro To Cellular Networks
Other than phones like Nextel's, most phones sold in the US have both 850 and 1900 MHz radios. So if they all receive the same bands then why can't you use any phone with any carrier?
That answer is that they often speak different languages. The phones use different languages to talk to the cell towers. Or, sometimes phones use the same language to talk to the cell tower, but use different programming languages to run games and other applications.
The different languages used for communication between the phones and cell towers are called protocols. Currently, US carriers concentrate on two different protocols. Sprint, Verizon and many smaller carriers use CDMA - a protocol developed by Qualcomm, and used primarily for newer cell phone networks in the Americas and East Asia (Korea, Japan, etc). Cingular and T-Mobile use GSM - which began in Europe and is the most popular protocol worldwide.
There are a few more protocols that are still in use in the United States. Nextel uses iDEN, a protocol developed by Motorola, but will be phasing this out. Some carriers still offer AMPS (analog) and TDMA, however they are both relatively obsolete, especially now that 3G systems are launching throughout the US and are being phased out as well.
Although they both use the same CDMA protocol, Sprint and Verizon use two different programming languages for the applications you can download. Manufacturers will build two models of the same phone but install different decoders for programming languages on them. These two different languages are called Java, which Sprint uses, and BREW, which is Verizon's choice. GSM carriers as well as Nextel also use Java for their programming language.