When you first launch Music/Zune, look for two musical notes at the bottom of the screen. Tap that and it will shuffle all the music on your phone.
Here's hoping that upcoming version of WP7 will bring more functionality to the music player. Current version is very limited/primitive compared to iOS and 'old fashioned' Zune player.