The cheapest option, and (from my experience) most reliable method of sending textmessages with an Arduino is using the Sony Ericsson cellphones that accept serial interface (old models). I used the T68i for this, but others work too. Interfacing through serial is easy, but it demands PDU format input for sending textmessages.
Sending SMS with arduino using this cellphone is cheap: i bought two through ebay for $5 and $7 respectively. I have used it for two HAB (high altitude ballooning) projects (Home - TimZaman.com), that sent me a textmessage with the GPS location on touchdown.
Something else you need is a datacable. I bought two for $3 through ebay. Just cut the wire and hook up the Rx, Tx and GND. The cellphones wants 3V, but 5V has always worked fine for me (just in case, put like a 1k resistor in the gnd line). Just turn the cellphone on and hook up the datacable and you're ready to go.
Anyway, the code is super easy; you just say something like sendsms("whateveryouwant"); and it sends it. Obviously you have to set a destination phonenumber somewhere else.
Anyway, the code is here:
any questions please put them in the comments of the blog that i regularly read.