Since iOS 8.4, Apple changed the way you shuffle music in the Music app. Instead of there being a large, easy to see button, the Shuffle All control is a bit hidden. Not much, but if you don’t know to look for it, you might miss it.
When you’re in the Music app, pull down on the display the see a Shuffle All control appear from the top of the window. Tap that, and you can start shuffling.