Mark,
If you have a compatible phone then Smith Micro sells software (Quicklink Mobile) & usb cable combo that will get you online. So, it'll work on a 12" PB with no pcmcia slot.
For example, with Verizon you need a plan that has "National Access". Odds are if you have Verizon then you have this already. It means you can get online and the only cost will be minutes from your plan (no additional charges, no Treo phone needed).
Basically, all this is is a usb-to-cel phone cable. The Smith Micro software works fine. Speed is based on Verizon's Nat'l. Access. It varies up to about 200k. I've found it fine for checking e-mail via web mail (browser based) access when for some reason a hotel does not have access.
Smith Micro QuickLink Mobile
PS. I see this software was listed further up in the thread. It referenced a card, again, just wanted to point out that with the right phone and the right plan you can do it for little additional cost (only the software/cable cost).