The current search function (product.views.do_search) creates a list of preformatted tuples with the search results. They include the item's type (Category or Product), name and url.
I would suggest saving the product and category objects into the search results. I'm using a dictionary for it myself - please see attached patch.
This will require some change in the search.html template - I included my example as well.
Reported by Czak