If the playlist sync over but the podcasts fail to play, it could be that you have your iPod shuffle set to "shuffle songs". You must switch to "play in order" for it to work.
From Apple Support:
Playing Audiobooks and Podcasts on iPod shuffle
When using iPod shuffle (1st and 2nd generation), if iPod shuffle is set to shuffle songs it will play all the audio files on iPod shuffle except audiobooks and podcasts. To play an audiobook or podcast, set the switch on iPod shuffle to play in order .
When using iPod shuffle (3rd generation), podcasts and audiobooks will not be played when content is played from All Songs. If content is played from a playlist synced from iTunes, audiobooks and podcasts will only be played if the iPod's switch is set to play in order . In addition to playlists synced from iTunes, iPod shuffle (3rd generation) will create a special playlist for each audiobook synced and one for podcasts. When accessing these special playlists, audiobook and podcast content will play whether the iPod is set to play in order or shuffle songs . Podcast are sorted by alphabetical order and then by episode date.