How do I combine search for categories and entries into one set of search results?
The reason you're getting an error when trying to merge the two search results is that they are not technically arrays, but elementCriteriaModels. To convert them to actual arrays you would need to use the find() method.

{% set entries = craft.entries.search(query).order('score').find() %}
{% set categories = craft.categories.search(query).order('score').find() %}
{% set results = categories|merge(entries) %}


The problem with this is that the sort order will be wrong (showing all categories and then all entries). Although you could potentially sort the results array using something like the supersort plugin.

The other option to consider is redesigning the database so that there is nothing in categories that needed to be searched for, which might simplify things in the end.