I did it with my Verizon 6700 with USB modem.. Very similar device. Here is how I did it:

Prior to pairing the 6700 with the N810 activate USB modem on the PDA.

Then pair the 2 devices - I started with the 810.
On 810 - Blue tooth devices - New - when you see you device, click on it - OK -On your PDA, enter the code that the N810 generates - on PDA hit finish

You N810 will display "Use this Phone for internet connection? "- Yes

On N810 - Operator Setup - Next - USA (or wherever u are) - Next -Pick you provider ( mine is Verizon) - Next -Finish

Close Bluetooth Manager on N810

On N810 Click on your wireless connection (upper right of Screen next to bat indicator) - choose Connectivity Settings - Connections - You should see your service provider (Verizon Wireless for me) -Click on your provider - select "Data Call" - Next - On the "dial up number" enter #777 -nothing to enter on the other tabs- finish - done (not sure if #777 will work with Sprint).

I could only get this to setup if I ran USB modem on my device prior to pairing. It works great on my setup..

Hope it works for you

Rich O