I have been wanting to do this as well so have done some preliminary looking into it. What you need is a Nokia mobile phone probably a 5110 or 6110 as these should be cheap s/h these days. These both have built in data modems and using a simple serial convertor which can be made for about £10 or bought for between £15-£20 can be plugged into the serial port on your linux machine. There are a few programs available with the best known one being gnokii http://www.gnokii.org/ or gsmlib http://www.pxh.de/fs/gsmlib/doc/index.html

Hope this is of some help.

Cheers,

Ben