When Shuffle is set to Songs iPod plays songs from the selected list (album, playlist, or library) in a random order. Songs are not repeated until iPod has played through the entire list. Pausing a song does not affect the random order. However, if you turn iPod off by pressing and holding the Play/Pause button it will not remember the random order or the selected playlist.
If you have Shuffle set to Songs, and repeat set to All, iPod randomly plays songs from the playlist. When each song in the playlist has been played, iPod plays the list again, this time with a different random order.
If you make make these selections: Artists > All > All, then press the Play button, iPod will choose an album at random and play it in its entirety. iPod will then shuffle to another album and play it in its entirety. Albums are not repeated until iPod has played through the entire list.
If you choose a song from the Songs list, iPod will play that song, then the remainder of the album associated with that song. iPod will then shuffle to another song in the Songs list, play it, then play the remainder of the album associated with that song. For example, if iPod chooses track 8 on an album with 15 tracks, Album shuffle will play tracks 8 through 15 of that album, but not 1 through 7.
iPod: About Shuffle
Learn about the Shuffle feature in iPod software 1.1 and later.