For reference, in foo_openwith's preferences, you would want the following as the "main parameters":
CODE
http://www.google.com/search?q="%artist% %title%"
replace the part in quotes with whatever you want to search for. (Obviously, this is for Google. I'm sure there's a similar search URL for other search engines).