We could also do with an SMS module to help with recovery once we've lost line of sight (LOS) with the payload (eg once it landed). One way we could do it is described here using $20 mobile phones. Basically we'd probably want the Arduino to sense a mobile signal, and send an SMS every 10 mins or so containing the position of the ballon. We could also arrange to send it an SMS to do stuff (how about sounding a very high volume piezo alarm - like a fire alarm) to help with recovery?
Update 28/2/13: The module here looks just the job. At 36g it's pretty light and it only costs $47 delivered! Just add a SIM and hook up to an Arduino. At low altitudes, you could also use it to stream video over 3G...

