I had to delve into the workings of iTunes Shuffle when I was stuck for a month with "only" about 15 GB of music on an external hard drive to listen to in iTunes. I set it to Shuffle and noticed that I kept hearing the same songs over and over, especially when I disconnected the external hard disk which I did every few days.
I soon realized that iTunes reshuffled the playlist every time i remounted the external drive. So to make sure I actually heard every song once before starting over, I did a Shuffle, then "Copy to play order" to preserve that one shuffle. Then everytime I reconnected the drive for some annoying reason it would start over at the first song again. So I'd go back in the "Most recently played" smart playlist and see where it'd left off, and jump to that song to pick up the same shuffle list again. That way I was finally hearing ALL the songs.
I still don't know what algorithm they're using, but there are several pseudorandom binary counting schemes that easily hit every song in a list once. For instance counting from 1 to 1024, but just reversing the bits of each number, will appear to jump around somewhat randomly in the list.