That would be a nice addition. Even a cellular modem without voice capability would be quite useful.
I know of 3 GSM modules that may be small enough to work with on a shield the size of the "TinyShield Proto Terminal Blocks" (I don't know the exact size of that board but it looks about 26x30 mm) - the uBlox SARA-U2 series (16x26x3 mm), the Telit UL865 (24.4x24.4x2.6 mm), and the SIMcom sim900 (24x24x3 mm)
Using the "TinyShield Proto Terminal Blocks" as a starting point, the connector and mounting holes for the shield would have to be shifted back towards the connector edge so the GSM module could be squeezed onto the board. A SIM card holder would need to be mounted under the board. A U.FL connector for the antenna, a TRRS 2.5 mm jack for ear/voice, and all other support circuitry should probably be put onto the bottom side of the shield. Many of these GSM module's features require lots of pins... this would impact what other shields could be used in the stack. These pins would have to be sussed out to see which ones could be ignored.
A good start on a wiring diagram and components for a Telit UL865 can be found at
http://www.mikroe.com/downloads/get/1921/gsm_click_manual_v101b.pdf for the MikroElektronika GSM click. I could only find code for a project using the Telit gm862
http://tinkerlog.com/2009/05/15/interfacing-arduino-with-a-telit-gm862/ which could be somewhat helpful.
A great project using the SIM900 is the Arduino Phone found on Instructables
Instructions: http://www.instructables.com/id/ArduinoPhone/?ALLSTEPSCode on GitHub: http://yexiaobo-seeedstudio.github.io/ArduinoPhone/
