Using the mac app, Music.app, I can go to the Music Store but how do I search for an artist or a song
In the Music app, click in the Search bar at the top of the left sidebar. When you do that buttons will appear on the right to select either Apple Music or Your Library. You can search for artists, albums or songs. Note that I subscribe to Apple Music, so your details may vary if you don't, but I think the search should work just as well.

I tried signing out and got similar results - plus an iTunes Store button! So give it a try.