The 1st and 2nd gen shuffle acts like a simple playlist. The 3rd and 4th gen shuffle is more like the "bigger" iPods. You can place a song more than once on a playlist, and a song can be on multiple playlists, but the song file itself is only stored once on the iPod.
However, the 3rd and 4th gen shuffle CAN use playlists. You can add a playlist manually, or by using automatic syncing. So instead of playing songs on the shuffle from the All Songs list, you can play songs from a playlist that is on the shuffle. You can place a song as many times as you want on the playlist. You switch between playlists on the shuffle by using the VoiceOver button (press and hold). This article has more information about using VoiceOver on the shuffle