It's actually pretty simple, and can be done both for the Autocomplete and the Instant Search results page.
1/ Multi-Category Autocomplete
You can follow our multi-categories autocomplete tutorial that explains how to perform the same query on multiple indices and display results in the same auto-completion search box.
2/ Multi-Category Instant Search results page
The easiest way is to duplicate your search code: doing a search on two indices is the equivalent of doing two separate search operations.
As a side note, searching on N indices will generate N search operations, which has an impact on the pricing.