Arduino does not have an IP stack, and the GSM modem type thing is just going to give you raw GPRS. This might be a way forward:
http://www.sics.se/~adam/uip/index.php/Main_Page I'm sure there are people that would be interested in a GPRS implementation to go with this.
The Ethernet shields and the like are low-budget IP implementations tied directly to their ethernet hardware and would be of no real help in dealing with GPRS. If you use an Ethernet shield, then you need a hub or router and an EVDO internet stick. You could likely get this combo working, but it would cost a bit.
If you don't mind paying $75 per year or so to operate a handset, you can receive infinite SMS messages with a PetroCan SIM. This is also the cheapest way I can find to send SMS at $25 per 250 for 4 months or $20 per 2500 per 30 days. My volume is such that the $25/120 day approach is better. I have an old Nokia handset wired to my UNIX computer and it sends and receives SMS, no problem.
Again, Howard Forums.