It takes a PDA/Smartphone . Tethering or Phone As Modem (PAM) plan not needed.
Here is what I have and how I do it.
Obviously you need a cellphone that is EVDO capable, and a unlimited data plan. It also needs to have WiFi capability. In addition to a EVDO data modem I have a Sprint Mogul (HTC Titan/6800).
As an added bonus, if your phone does not have wifi, you can still use the program to tether with a USB cable.
Another competing program is called WalkingHotSpot. This essentially does the same thing albeit with different purchase options (monthly,yearly) and also has a 7 day trial.
This program supports Symbian based and Windows Mobile 6 Professional and above phones.