検索 is typically used when searching, or looking up in, or retrieving from some kind of data store, which these days more often than not is a computer database or of course the Internet. Translating it as "search" is almost never wrong (although in a database context it could be "query"). In the example you give, depending on the level of colloquiality you're shooting for, I'd go with something like "Could I ask you to do a web search?"
探す is of course a much more general term. As a rule of thumb, when searching on the net, 検索 would tend to be used to refer to a single search possibly with particular keywords, whereas 探す in that context (when not being used to mean "find") would more often indicate a whole process of searching multiple sites and keywords.