For some reason (perhaps due to worries about file size), the iPod shuffle will not autofill podcasts. As stated in the help menu:
If you have an iPod shuffle, iTunes-enabled mobile phone, or third-party music player, you can only load podcasts onto it manuallyThis is annoying if you want to automatically update your shuffle with podcasts from, for example, a smart play list. It can be fixed manually by selecting the podcast (or podcasts) and unchecking the Skip when shuffling box in the Options pane of the Get info dialogue box. A better way is to use this short AppleScript, which does this for you. Copy and paste it into Script Editor, then save it in the ~/Library » iTunes » Scripts directory, as you can then run it from the Scripts menu in iTunes.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20070218041737189