I have always stuck with [探]{さが}す for "search", but in an anime I heard one of the characters say
インターネットを[検索]{けんさく}おねがいしてもいいですか。
I suspect that one of the differences is that 検索 is more likely to be used when speaking of an internet search. Is that correct? And are there any more differences between the two words?
検索 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.