Showing NP-hardness by reducing from a search problem I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem.

But we can also have NP-hard search problems. For example, it is claimed in the introduction of this paper, that finding a $k$-coloring of a $k$-colorable graph is NP-hard for $k \geq 3$. Let me call 3-COL-SEARCH the problem in which we are given a 3-colorable graph $G$, and have to output a valid 3-coloring for $G$.

For concreteness, suppose $X(G)$ is asking for the minimum number of operations to achieve something fancy for a graph $G=(V,E)$. We wish to show computing $X(G)$ is NP-hard. Technically, I should be able to do this by a reduction from 3-COL-SEARCH.

But what would we show in the reduction now? If this was a decision problem (3-COL) we are reducing from, perhaps we'd be showing "the graph $G$ is 3-colorable if and only if $X(H) \leq |V|$, where $H$ is some new graph we construct". But now I'm confused: would we show "we can find a 3-coloring for the 3-colorable graph $G$ if and only if $X(H) \leq |V|$"? 

Is there perhaps some paper or resource that gives an example of such a reduction as well? I'd guess this is not so exotic.
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.