Many music players have done this for a long time. In fact I believe that's part of the reason why they refer to that function as "shuffle" rather than "random"
That depends entirely on the implementation. There's no one rule for how developers should implement shuffle.
When I was writing my in car entertainment system (it's not as good as it sounds!) the first metric that was shuffled was the artist, followed by weightings for albums.