While I'm not on a Mac, I'm doing exactly what you're asking about right now.
I have an Alcatel OneTouch 715 mobile, and GPRS data access through Vodafone Hungary, connected via IrDA to my laptop. I also have a Siemens S55 mobile with similar access through PannonGSM, and it connects via Bluetooth (I'm waiting for the Vodafone contract to die - thus the 2 phones).
Access speeds are comparible to a 56kbps land-line connection (maybe a little faster). Once thing to watch out for is that GPRS data streams are compressed on the provider's end. You also have to worry about data usage, as there is no such thing as "unlimited" - my Vodafone HU account is 200MB/month and my PannonGSM account is 300MB/month. Granted, my experience only deals with Hungarian providers, so it could be different outside of the country. I highly doubt you'll be using iChat Audio over GPRS, but I'm not yet familiar with how much it compresses data streams (hopefully I'll know soon enough
: )
I know in the US, Verizon Wireless (55% owned by Vodafone UK) is testing a high-speed connectivitiy that will offer 300kbps-500kbps in supported areas using something that is like GPRS over 802.11. The test cities are Wasington, DC and San Diego. It's possible that Vodafone will introduce something like that in Europe.
It's worth having the ability to be connected where-ever when WiFi isn't an option (as it isn't pretty much ANYWHERE in this country except Györ). If the phone supports GPRS, it'll work. Pretty much any GSM phone that has been released in the last 1-2 years, but double check. Both of my phones work well, and Sony-Ericsson T68i (the one Steve Jobs showed during the keynote introducing Jaguar), T61x series, and Pxxx series phones have been known to work exceptionally well. You can connect most phones via USB, IrDA (if you dont have IrDA, you can get IrDA-to-USB usually cheaper than a phone's USB data cable), or Bluetooth. Personally, I prefer Bluetooth.
For providers, the 2 largest in Europe (as I assume that's what you mean "overseas") are T-Mobile and Vodafone. T-Mobile owns the most networks (over 60% of Europe AFAIK); Vodafone has the most customers. Both are quite good.