Yeah. The random is pseudo-random of course, that's how computers work. As soon as you activate 'random' it randomizes the entire playlist, so it knows what songs will be next and cache's them.
It's important to note that on the iPod you are *always* playing a playlist. Even if you browse to your favorite artist and just play all music from that artist, it's a 'playlist' even though it's not stored as one. If you switch 'playlists' by actually changing playlists, or genre's, or artists, etc. than the HD will have to spin up again because the songs that were in the cache are no longer the songs you wanted to hear.
Why does this matter? Well if you jump around a LOT like I do, than it will slightly reduce battery life (Not total battery life, IE $99 replacement, I'm just talking about you'll get 6 hours on that charge instead of 8). This has never been a problem for me, however, but I thought I might as well disclose it. A way to get around this is to make a "on the go" playlist, which is generally what I end up doing.
Why do you ask? Do you have reservations about the 'Pod?