what happened to the shuffle option in iTunes
You need to create a playlist with all of your music in iTunes, add that playlist to you iPod, and then when you select the playlist, you are given the option to shuffle the playlist at that top of the list.