I'm using the O2 network on contract and Ubuntu 10.04 on an Eee 1005HA for this guide.

First, ensure your internet connection on your phone is enabled.
Attach N900 to computer via USB and choose PC Suite on the phone.
Right click the networking icon in the tray on Ubuntu.
Tick "Enable Mobile Broadband".
Now, left click the icon and choose "New Mobile Broadband (GSM) connection..."
A new window will appear. Hit the Forward button.
Choose your country and hit the Forward button.
Select your provider and hit the Forward button.
Select your plan and hit the Forward button.
Then hit "Apply" on the next page.

Close the window, left click the network tray icon and hit your new connection.

Et voila!

This is posted via my O2 connection, so I know it works...