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:
Ask Different is a question and answer site for power users of Apple hardware and software. It only takes a minute to sign up.Sign up to join this community
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.