Tethering Edge to cell phone

I have a Blackberry Storm....very disappointed in it, so it's time for replacement.

I'd like to pick a smart phone that I can use to tether my Edge so that it (the Edge) has Wifi connectivity when I am on the road.

Has anyone accomplished this yet? What hardware and software were you using?

Thanks in advance,

Garrett