At first, the harware is easy. Just an Arduino and a GSM Modem. Connect them through the serial port, and read datasheet from the GSM modem to check the proper AT commands to send SMS's
I'm afraid not. All the internal protocol requirements to send an SMS (GSM media access, SIM control, radio signaling, etc) is what a GSM modem provides. And also, with a GSM modem you can do more things, right, but a GSM Modem which is cheaper because only sends SMS, I'm afraid it doesn't exist...
There is another way which is using a internet gateway, but they usually have a cost.
There are two ways to send SMS. One is to have a complete GSM chip set, and send the SMS as if you were a phone. To do so, you need a SIM and the service cost that goes with it. It's just like a phone, and costs what a phone would cost to send an SMS.
The other way is to use an Internet gateway. You pay by the message, and there is typically no other cost. For a large volume of SMS, it's always cheaper to use a gateway. For a really small volume, it's always better to use a gateway, because you don't have any hardware costs.
In between, it depends. If the hardware cost + the service cost is low enough, it might make sense to use the GSM modem. Otherwise, the gateway is cheapest.
There are a lot of gateway services around, so you need to spend some time with Google.
Note that you DON'T need a GSM modem to send SMS, you only need a GSM phone chip set. SMS doesn't use the data service. However, it's hard to find the parts you need in a form that is reasonable to use in a project; you almost always end up using the modems, because they are designed for the task.
Will the Arduino be connected to a PC, or other device capable of sending SMS?
Someone recently posted a thread about a project that uses a cheap "pay-as-you-go" GSM phone with a serial interface to send and receive SMS messages about a GPS also attached to the system. Thanks to the subsidy from the Evil Greedy Giant Phone Companies ;D (who anticipate getting their money back quickly from your text-addicted teenager), the phones are cheaper than buying modem modules.
Let us know how this works out, I'm planning on the same idea as a Christmas present for my father. He has a lake house that often goes weeks and sometimes months without anybody going there. There's no internet in that location (there is a wifi signal from another house across the street, but I don't know the guy and don't want to rely on that signal).
The main function of this is to know if it's getting cold enough to freeze the pipes. I'm planning on having a data logging system with an SD card that will constantly log the temperature and other variables. One such variable would be some kind of sensor that can watch the float valve on the oil tank, I'm thinking 10 evenly spaced IR photodiodes along the sight glass to monitor the amount of oil in 10% increments. Another function would be watching an opto-coupler connected to the main power to detect when the power goes out.
Eventually, I'd like for this system to monitor as much of the house as possible. I'm thinking a motion sensor in the kitchen (since you have to go through the kitchen to get anywhere else), this could both work as a security system and off the data log sheet could just tell us whenever the last time there was somebody in the house was. It may also some day have a way to set the temperature via a text message so say I'm going up there in the winter to do some skiing, I'll send a message telling it that half an hour before I plan to be there to turn the heat up to 70 so the house will be warm when I get there.
This seems like the perfect first long-distance project where I would be communicating with an Arduino 110 miles away via text messages. I'm thinking I could set it up where I send it a message requesting something and it sends one back with the response.
I'm looking at this http://www.dealextreme.com/details.dx/sku.12057 as being the modem, the neat part is that since it essentially is a cellphone, it even has a jack for a speaker and a mic, I'm thinking about maybe getting a text-to-speech system like the SpeakJet and connecting it through this jack to do a DTMF-controlled voice prompt system where I could call the number and go through the menu to hear or set what I want.