The simplest explanation that I can muster for cellular data:
T-Mobile - GSM for voice, GPRS for data, speeds up to 3.7 KBytes/second, $20 a month for unlimited use
Cingular - GSM for voice, GPRS and EDGE for data, speeds up to 20 KBytes/second if you have an EDGE capable phone. $20 a month for unlimited data on a phone (and a PocketPC or laptop tethered by Bluetooth)
Verizon - CDMA for voice, 1xRTT for data, speeds up to 12 KBytes/second, $80 a month for unlimited use, or you can use your minutes. Only one Bluetooth phone available, and nor a very good one.
Sprint - CDMA for voice, 1xRTT for data, speeds up to 15 KBytes/second, $15 a month for unlimited use on a phone, no Bluetooth phones available
My advice would be to go with T-Mobile or Cingular. The CDMA providers are way too restrictive, and have almost no Bluetooth options. Either of the GSM providers will have plenty of Bluetooth phones for you to choose from.
For choosing actual phones, try out this site:
http://www.phonescoop.com/phones/finder.php