If I download podcasts on iTunes, should they download on my iOS5 3GS automatically, over the air? I was under the impression this was a killer feature of iOS5. I'm running the latest versions of OSX, iTunes and iOS.
iOS 5 does not do automatic Podcast download or subscription. OTA downloads are available only for Music, Apps and Books under the Settings -> Store screen.

For podcast management, you're still required to sync with iTunes. This might change in future versions, but it is not in the current version, nor can I find any references that it will be.