I travel quite a bit for work, including internationally. My experience is this:

Don't count on free Wi-Fi at all. Very few places offer it these days. The only places I find it now are a couple chains in the US, such as Panera Bread, Caribou Coffee, and Corner Bakery. In Europe, I've yet to find a free WiFi outside of some home user with an improperly configured wireless access point (meaning, they never set up security on it). Even those are becoming less common -- have Netgear/Linksys/etc made newer versions of their access point firmware require the user to set up security now?

As far as the hotspot providers go, there is no one provider that really covers all locations cost-effectively. In the US, T-Mobile has the best coverage for general walk-about considering all the Starbucks/Borders/etc on every street corner. However, travel outside the US and they are completely unusable due to the high roaming charges (18 cents/minute, even when using T-Mobile overseas). In Europe, Boingo seems to have much better partnership coverage. Boingo also has most of the major airports in the US (either through their acquisition of Concourse, or via roaming partnerships). So in addition to the unlimited T-Mobile plan, I also have a Boingo Global plan.

It may seem like a lot to pay for both a T-Mobile and a Boingo Global account, but consider situations like this: I've stayed in Hotels in London, which were serviced by Orange's wireless network (e.g., the Novotel line of hotels). Orange wants 20 euros a day for wireless access, but are a Boingo partner. With the Boingo Global account, I was able to connect to the Orange network in the hotel for no additional charge via my Boingo Global account. So in 2 days (I was there for a full week), the Boingo Global monthly fee "paid for itself" vs. if I had to pay 20 euros for each of 6 days...

On my laptop, the Boingo Wireless Client is very handy, as it auto-logs you in to any Boingo partner's WiFi. In the US, you can also configure it to auto-login to T-Mobile hotspots via their 802.11x SSID (tmobile1x). So one connection manager automates login to both my hotspot accounts. I really wish Nokia would get Boingo to port their connection manager to the N800, as it is just begging for a proper wireless connection manager. But for now, you can still log in to Boingo partnered hotspots using your Boingo credentials on their web access portal page. As was previously mentioned, some of them have a "pick your roaming partner" selection when you enter your credentials. For others, you may have to modify your username. E.g., "boingo/<username>" or "<username>@boingo.com".