In the old version of the music app you could shuffle all songs when songs were selected:
This feature seems to be absent in iOS 8.4 and the new music app:
Recently Addedalbum artwork is a title which by default reads
Artistsit is a pink drop down menu.
Songsfrom the list.
The above solutions didn't work for me. What worked for me was after starting a song, I tapped the bottom bar that shows what's playing. Upon tapping, a window with the album cover appears along with the player controls, including the shuffle and repeat buttons.
To shuffle all music select Artists, Albums, or Songs, press play on the ear buds
In other modes of play the shuffle is a toggle. It will remember if its on or off. If its on pressing the picture in the Artists list will play all their music shuffled. If shuffle is off it will play all music starting with the most recent album in album order.
The same is true with the Album list. Shuffle on, press the picture, the songs of that album are shuffled. Shuffle off, songs play in album order.
You can also use the command "shuffle music" with siri