Posting this here for the sake of future google-searchers; the discussions I found on the Apple support fora didn't help much.
TL;DR: Tether your phone to your iTunes machine. In iTunes, click your phone's icon. Click the 'Podcasts' tab. Note the "Include Episodes from Playlists" checkbox list, which I do not believe existed before iOS 5. Adjust its values needed, then hit 'Sync'. Boom.
Background: I use the "Music" (neƩ "iPod") functionality of my iPhone mainly to listen to the most recent episodes of my favorite podcasts while I commute, exercise, wash dishes, and so on. With iOS versions 2 through 4, I found that a great way to accomplish this involved creating a Smart Playlist in iTunes, instructing it to fill itself up with my most recent unplayed podcast episodes. I'd then ask it to always sync this playlist with my phone when it was able, et voila: a fresh batch of new podcasts after every sync.
This stopped working with iOS 5. I had noticed that while the playlist continued to show up on my phone, it was always empty after every sync, even if it was full of the correct new podcast files on my desktop machine's iTunes.
Solution: Unless I'm mistaken -- I didn't empirically document every step of my research, here -- the solution lies with a new checkbox list labeled "Include Episodes from Playlists". You can find this in iTunes, under the "Podcasts" tab, while your iPhone is connected to your computer and selected in iTunes.
If you were having the same problems as I, then you'll discover that your podcast playlist is unchecked. Check it, then sync again.
Everything should now work as you remember. Enjoy!