Correct answer was pointed to in the comments by RossC. Thanks! I'm writing my own here since it's been a while and he didn't write a proper answer I could have selected(!).
I did a bit more research to expand on what he found, while also clarifying the original issue which was partly PICNIC...
According to here it may only be in the US and depend on what version you have.
reddit.com/r/Android/comments/14r6m7/… Apparently the 'clock' icon will do it
reddit.com/r/Android/comments/1p7d0w but I don't have that on mine ...
So the second link above gives the answer: On the device one cannot access the Music Search History from anywhere but thru the widget's "clock" icon. Since I only had the widget placed in the lockscreen so I did not see the icon while I was actually actively using my phone (unlocked) to look for its history. I can only access the history from the lockscreen widget, that is unless of course I put the widget on one of my panels, which is unnecessary since Google Now can also do music search (just say "what's the song" or similar).
Apparently the Music Search is also unavailable in some countries, so YMMV.
Also, I found out here you can also access your sound search history on your desktop/laptop by logging into your Google Account and going to this hidden(?) "auto-playlist" link (I couldn't find anywhere in Play Music site UI):
Hope this clears a few mysteries regarding Sound Searches and its widget.