Methods of turning a decision problem into finding the certificate?
The main method is self-reducibility. Suppose that your problem is of the form "there exists an object $x$ such that $P(x)$". Consider some partition of the set of all possible objects $O$, say $O = O_1 \cup \cdots \cup O_m$ (here $m$ should be "small", i.e. polynomial in the size of $x$). If the problem "there exists an object $x \in O_i$ such that $P(x)$" can be reduced to your original problem, then you can use a recursive approach for finding some certificate. The reduction should have the property that a witness for the reduced problem implies a witness for the original problem.

SAT, the example in the question, has exactly this property. In this case, $x$ is a truth assignment, and $P(x)$ states that $x$ satisfies some formula. For each variable $x_i$ we can partition the set $O$ of all truth assignments into $O = O_{i,true} \cup O_{i,false}$ according to the value of $x_i$. The problem "there exists a truth assignment $x \in O_{i,val}$ such that $P(x)$" (where $val$ is either $true$ or $false$) is also a SAT problem. We can use this to figure out a truth assignment satisfying $P$.

A more interesting example is 3-colorability. In this case $x$ is a 3-coloring and $P(x)$ states that $x$ is a valid coloring for the input graph. For any two unconnected vertices $v,w$, we can consider the partition $O = O_{v=w} \cup O_{v\neq w}$, according to whether $x(v) = x(w)$ or not. We can reduce the problem "there exists $x \in O_{v=w}$ such that $P(x)$" into an instance of 3-coloring by merging $v$ and $w$. We can reduce the problem "there exists $x \in O_{v\neq w}$ such that $P(x)$" into an instance of 3-coloring by adding the edge $(v,w)$.