If you create a regular playlist in iTunes, you have to update it manually. Remove old podcast episodes and add new ones, put them in any desired playlist order.
If you want to automate the process, you can probably get what you need using a Smart Playlist. To create a new Smart Playlist, click the plus sign below the iTunes sidebar, and select New Smart Playlist.
Check the box for Match ALL of the following rules. Then add the rules needed to get what you want on the list.
The first rule you need is to put podcasts on the playlist.
Media Kind - is - Podcast
To exclude podcasts that have been played
Plays - is - 0 ("zero")
Those two rules should give you a playlist with unplayed podcast episodes. To include only specific podcasts, not all podcasts, use the checkbox for Match only checked items (and you'll need to uncheck the podcasts you don't want on the iPod).
Also check the box for Live updating.
Click OK. See if that Smart Playlist creates a playlist with the podcast episodes you want. If you need to change the rules, right-click on the Smart Playlist and Edit Smart Playlist. You can post back if you have some other ideas that you want "translated" into rules.
To put the podcast episodes in order by Date Added, select the Smart Playlist in iTunes so that you see the list of items. If Date Added is not one of the columns shown on the list, right click in the list's header area and select Date Added. To sort by Date Added, click on Date Added in the header. Click on it again, if you need to reverse the order.
Sync that Smart Playlist to the shuffle. It should play in the order shown in iTunes.
An iPod shuffle is meant to be a simple device. It doesn't have a screen (where you can change a bunch of preference settings), so it is designed to operate in a certain way. If you need the iPod to work more flexibily, you may want to get an iPod nano instead.