Showing NP-hardness by reducing from a search problem
Basically, you pick any convenient decision problem known to be NP-complete and reduce from that problem to 3-COL-SEARCH.  In other words, informally, you prove that if it was possible to solve 3-COL-SEARCH in polytime, then it'd also be possible to solve that other problem in polytime.

For your particular example, a very convenient choice of decision problem is 3-COLORABLE.  It's known that 3-COLORABLE is NP-complete.  Now you just need to reduce 3-COLORABLE to 3-COL-SEARCH.  The reduction will be super-easy: take the hypothetical algorithm for 3-COL-SEARCH, run it on the graph, check whether it has output a valid 3-coloring or not, and if yes, output "Yes", otherwise output "No".  This will be a valid solution to the decision problem 3-COLORABLE, if the hypothetical algorithm correctly solves 3-COL-SEARCH.

Usually you can do the same thing with other NP-hard problems: often there is a natural decision problem associated with it, so you prove that the decision problem is NP-complete and then find a reduction from the decision problem to your search problem.



The other thing that's going on in your example is that, the way you defined 3-COL-SEARCH, it's a promise problem.  A promise problem is one where we have a promise that the input will be within some set -- and the algorithm is allowed to do anything it likes on other inputs.  Promise problems can be a bit counter-intuitive, or at least harder to think about, from a complexity-theory perspective, so if you're able to frame your problem so it's not a promise problem, I think that will usually be cleaner.