What GSM / Cellular shield for Arduino

FWIW, I have had very good luck with the Seeedstudio version. Geekonfire also has a model.

Whatever module you want to consider, research the underlying chip and libraries! For the sim900 there are a number of libraries and examples out there that you can follow along. The AT manual also gives you the commands you'll need to use in order to start a GPRS connection, send an SMS, etc

Also, depending on where you live, it might make sense to use a M2M Sim card, ie one designed specifically for applications like this one. I had good luck with the unit from embedded works.