If you're still using iTunes, you've probably noticed that the shuffle feature doesn't always seem the most random. In fact, at times shuffle may have seemed completely set in stone (which, of course, would make no sense). As one user at AskDifferent points out, there's a method to this madness -- and it's easy to fix your non-random shuffle.
Essentially, when you turn on shuffle, iTunes creates a randomly generated shuffle order of your entire library (assuming that's where you turned on Shuffle). While shuffle remains enabled, this "random" order will remain static -- that is, if Let It Be precedes Like a Rolling Stone, it will always precede it, no matter how many times you restart playback.
The trick to reshuffling your library is simple:
You uncheck and recheck the shuffle button. Doing this causes iTunes to recreate the random traversal path through your playlist (or entire library). It re-seeds the random number generator.
If you never uncheck and recheck the shuffle button the order never gets regenerated so things will start to seem non-random.
So there you have it. A simple solution to reshuffle your iTunes playback.
Why isn't iTunes shuffle random? [AskDifferent]