When it came to light that law enforcement has issued millions of annual requests/demands to the wireless carriers (AT&T, Verizon, etc) to hand over user data, we all got a little concerned. Our carriers know everything about us, and according to findings by Rep. Markey (D-MA), "Information shared with law enforcement includes data such as geolocation information, content of text messages, wiretaps, among others."
But! We have weapons. Here are some tricks to help protect your privacy.
THEY CAN SUBPOENA YOUR TEXT MESSAGES
The basic idea: you can encrypt your text messages so even if they're handed over to, you know, whoever, they won't be readable. It's password protection, really.
iOS: Your friends will hate you, but Encrypt SMS is a good tool for iOS. It costs a buck, and will encrypt your text message with AES-256 security, the same basically unbreakable encryption used by Julian Assange to protect his "thermonuclear" insurance file. Both you and the recipient have to have this app installed, and the messages themselves are password-protected. This should protect you from unwanted spying from your carrier.
THEY CAN TAP YOUR PHONE CALLS
Law enforcement has also been after the content of phone calls. Turns out you can encrypt those too, though not quite as easily.
iOS: The big player here is CellCrypt, which is really designed for government use more than consumer use (they have a hefty yearly fee, for example). Also, if you are paranoid, you might note that CellCrypt is cuddly with Verizon. You could try Kryptos instead, which also has AES-256 encryption and costs only $10 per month extra.
Android: WhisperSys also makes an app called RedPhone, which encrypts your phone calls end-to-end. Pretty sweet!
THEY CAN SEE EVERYTHING ON THE NETWORK
...So don't use the network! You can use Wi-Fi for most communications, especially if you live in a city with lots of hotspots. Of course, that comes with its own headaches--Wi-Fi hotspots are very easily hacked--but at least you won't be dealing with the carriers. And given that the carriers seem okay with giving "tower dumps"--basically, all of the info from one tower, which could mean the data from thousands of users--it could only help your privacy to stay away from those towers.
Apple's iMessage, which communicates between Apple devices, uses a data connection that is not routed through your carrier's servers the way SMS texting is. It'll take advantage of Wi-Fi if you're on a Wi-Fi network, which is a good thing to do whenever it's available--it's much harder for your wireless carrier to monitor (or, less scarily but more annoyingly, to wildly overcharge for) Wi-Fi use. BlackBerry Messenger, which has its own encryption, is similar--although its encryption doesn't work when the police seize your phone.
You could try a VoIP option to replace your carrier-monitored phone calls, but those are not always more secure. TextPlus and Talkatone, for iOS, Android, and Windows Phone, all set you up with a new number/address and allow you to make phone calls and send text messages over a data network like Wi-Fi. But! According to their privacy policies, they also store your messages and usage history, and will hand over that data if needed--just like the carriers. So encryption is really more important here than which service you use. CSipSimple is a VoIP app with much more intense security--it sets up its own container for the call, while apparently not interfering with the actual content of the call at all.
THEY CAN TELL WHERE YOU ARE
One of the scariest bits of information carriers (and thus law enforcement) has access to is your precise location, which can be gotten both from precise GPS coordinates and from tower triangulation--figuring out where you are based on how strong your signal is from each of several towers. This causes well-deserved freakouts every once in awhile. There are ways to keep your phone from knowing where you are, though. Both iOS and Android have fairly simple ways to opt out of location tracking in the settings.
Android: Go to Settings, then Location Services. Uncheck all of the boxes.
iOS: Go to Settings, then Privacy, then Location Services. Unswitch all of the switches.
The problem is that both Android and iOS keep your location cached on your device, which could be bad if anyone every confiscates it. If you root your Android device or jailbreak your iOS device, you can find apps to get rid of all that data. Lifehacker recommends Location Cache for Android and Untrackerd for iOS.
Once that's all taken care of, perhaps you'd like to go old-school with an offline map? Galileo is a decent one for iOS, and Android users can just use the offline version of the built in Google Maps. Or they can try one of several others, like MapDroyd.
And, of course, you can just throw your phone into airplane mode when you're not using it to prevent it from gathering any data.
Drive over the Manhattan Bridge at night on a weekday. Heave your phone into the East River. Buy a beeper, and only use pay phones. Never use the same pay phone twice. Congratulations, you are safe.