I have an N73 paired with a N810 on 3 with no problem. Its an XSeries phone so I get 512MB data (I have the modem as well for use on the other computers, but a different PAYG contract on that).
The N95 will connect fine on 3.
In connections, start a new connection
Call it what you like (3 for instance)
select 'Packet Data'
Hit Next
Select 'three.co.uk' (without the quotes). Note that if you did this with the wizard it will put a space at the end and it will not work. Clear it and type it in yourself. No spaces
dialup is '*99***1#' (but *99# will probably be ok)
user and pass is blank