I'm posting this up mainly for myself to use in the future, but also for anyone else who might be interested. To search the shops here on Shapeways I've come up with these methods.
To search for just a single tag, the only way I could find is to go to one of the products in your shop and make a temporary tag that you want to search for and then just click on it when out of edit mode. When you're done searching you just go back to that product and delete the tag.
Post up any search methods you come up with too if you want! Let us 3D print the universe. Oh wait! Maybe we already have!