I just thought I would point this out to people, since I haven't really heard too much about it, and I was wanting to do this for some time now.
This site has instructions and automated applescripts for sharing your Mac's internet connection via bluetooth. I'm using it with my 12" powerbook and my Clie PEG TG-50 and it works much better than I thought it would. The only problem is that you have to disable bluetooth syncing while you are sharing. But aside from that, it's great. The speeds are faster than I thought and the range I get is not too bad (seems to cover my apartment anyway).