There are a handful of services that bring podcasts to mobile phones over the phones data connection.

Unfortunately, navigating the phone that way is really hard.

I think there’s an easier way.

Update 31 Aug 2007:
I love the internet. If you wait long enough, the things you’re looking for will find you:
“Podlinez is a free service that lets you listen to podcasts on your phone.”
via Dave Winer via Nathan Rein