Google Play Music has a new feature called "I'm Feeling Lucky" that creates a radio based on your listening history. If you subscribe to All Access, Google includes a lot of songs that aren't in your library, otherwise the feature is a fancy name for "shuffle".
Here are some screenshots from the Android app:
There's a "dice" animation while the playlist is generated:
You can reorder the songs, remove some of them or add all the songs to a playlist by tapping "save queue".
You can find a similar feature in the desktop interface: go to "Listen Now" and click "I'm Feeling Lucky Radio".
You get a different "Feeling Lucky" playlist every time you roll the dice and the songs from the playlist are usually related. Here's an example of Eurovision-related playlist:
Click "Refresh station" and you'll get a completely new playlist:
For the old-fashioned shuffle feature restricted to your library, go to "My Library" and click "Shuffle My Library". In the Android app, go to the "Songs" tab from the "My Library" section and tap "shuffle all".
{ Thanks, Zachary. }