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.