How to connect the Arduino with Twitter via GSM/GPRS?
You can get a gsm/gprs module from sparkfun.  It looks like that'd be pretty easy to get going.  You would, of course, need data service to run it.