Oleg has written up a project detailing how to get your Arduino talking to an inexpensive USB cell modem (~$25 from DealExtreme, among other retailers). It’s based on a BenQ M23 GSM/GPRS wireless module and uses a standard AT command set.
This is the cheapest we’ve seen for a plug-and-play cellular solution, so it’s definitely a good resource. His site walks you through the setup process and provides example code plus a complete library, so if you’re looking to do something similar, check it out.
The SIMCom SIM900 GSM module isn’t very well documented (in English, at least), but it is dirt cheap. If you fancy putting cellular communications in your Arduino project, there are a few intrepid pioneers that have paved the way.
Seeedstudio sells a GSM/GPRS shield utilizing the SIM900, and have a well-developed wiki page with getting started tips, a walkthrough, and plenty of sample code.
If you’re looking for more of a drop-in solution, Open Electronics has a library to talk to a similar shield with the same SIM900 module. It’s unclear if that particular shield is still for sale, but the library should be adaptable to Seeedstudio’s version or others without too much work.