Here's the front page of the Music Store as seen on a PC:
And shots of the store seen on a Nokia N95 8GB:
Interestingly, the store client seems to be a customised version of Web, although Web itself exists independently and you can run a browser session elsewhere at the same time.
My searches for some of my favourite bands produced patchy results. Your mileage will vary though! Anyway, let's try and buy a track, download it and then play it:
All pretty smooth, although I did cheat slightly by using Wi-Fi rather than 3G data!
Finally, here's a YouTube Video (courtesy of nokiacreative) showing the music store in action, also on an N95 8GB:
Other devices are likely to be supported in the near future.