While it’s easy to shuffle an album, a playlist, or all the music by a given artist in iTunes 12, shuffling your entire music library isn’t available from the usual controls. But there are two ways you can do this.
The first method involves using iTunes’ menu controls to turn on shuffle: choose Controls > Shuffle > On. Then display your music in any view, making sure to not select anything; click the Play button at the top-left of the iTunes window, and iTunes will start shuffling all your music. If you have selected something, such as an album or artist, iTunes will only play the selected item in shuffle mode.
The second method is accessible from the Playlists sidebar; to display this, go to your Music library, then click Playlists in the navigation bar. Right-click on Music in the sidebar, then choose Shuffle. If you click on a playlist in the sidebar, only that playlist will be shuffled.
Note that if you start playing your music in shuffle mode when your are in, say, a specific genre, you’ll see in the Up Next menu (the three-line icon in the iTunes LCD) the upcoming songs from that genre. Select a different genre, and don’t change anything else, and check the Up Next menu again: the upcoming songs will be from the genre you have just selected. This has repercussions if you are starting shuffle play while viewing music one way, but want to browse your library; the shuffled tracks won’t be the same as what you may have expected. I’m seeing this when in Songs view, selecting a genre using the Column Browser; if I’m in Genres or Artists view, this change doesn’t occur. (So I assume it’s a bug.)
Personally, I usually only shuffle playlists, or, sometimes, artists. But if you want to shuffle your entire library, you can use one of these two methods.