You can find a Motorola C168i on Ebay for less than 10 dollars. The simplest way to get service for it is to buy a pay-as-you-go SIM card, at Radio Shack for example. While you're there you can also pick up the 3/32 plug; unfortunately, they don't have any information on the packaging but I've included a figure here for your reference (see left).
Here's a step-by-step on how to make your "breakout wire" and plug it into your Arduino.
Tools: soldering iron, wire clippers, wire strippers, a soldering stand is helpful
Bill of Materials:
Now try out the GSMSerial example library to make sure everything works fine (in Arduino IDE, go to File>Examples>GSMSerial>GSMSerial_Example