Actually it's not that hard, I've done it before - once the account was set up (15 minutes) the SMS was integrated and tested in about an hour. He's certainly not opening his own SMS gateway with $500 so he's probably using a service where you get a 5 digit number that customers include in their texts (everyone has seen this I'm sure).
The companies that supply this tech usually have a very easily integrated API so hooking it up is no more complex that hooking up to something like Twitter, in fact usually much simpler. Speaking of which I'd just hook it up to Twitter and let them be the gateway, saves a bunch on SMS fees (which cost you incoming - although this might be different in Australia).<p>Advertising is a pretty easy hook up as well, depending on the service.<p>Take a look at glunote.com, it's something that I threw together over a rainy weekend (and it certainly looks like it). It's for taking notes using Twitter and is probably at least as complicated as what he's doing. I'm sure there are a lot more examples around.