I've tethered my N95 with my N800 successfully....the N800 detects the phone and sets everything up automagically.
Works like a charm. The plan I have is T-Mobile's $40-a-month for 1000 minutes, unlimited nights and weekends and with their $30-a-month unlmited internet.
Yes, their EDGE speeds are pathetic compared to AT&T's newly-revamped EDGE (yes, I've used BOTH in the past 30 days) but T-Mobile is a little more "flexible" with my globe-trotting work/lifestyle.
And having an unlocked N95 with PAYG chips for Europe/Africa/ME works wonders.