I can't find any definition for the word either in the book I am reading or online. What exactly does certificate mean in the context of computational complexity? For instance:
[...]The above algorithm is similar to search algorithm. The important difference is that we do not try every possible certificate, instead this algorithm simply chooses one possible certificate and checks to see if it is good. [...]
I'm not sure if more context is needed. Reference: Complexity and cryptography, an introduction by John Talbot and Dominic Welsh, chapter four, probabilistic computation.
It’s easier to give examples than to make a precise definition that covers all uses and is reasonably comprehensible. Consider the subset sum problem: given a set $S$ of integers, is there a non-empty $Z\subseteq S$ such that $\sum Z=0$? This problem is $\mathsf{NP}$-complete, so in general it’s hard to solve. In particular, there’s no fast way to show that the answer is no. If the answer is yes, however, and you just happen to pick a $Z\subseteq S$ whose sum is $)$, verifying that $\sum Z=0$ is easy and fast. Such a subset $Z$ is a certificate (or witness) of the fact that the answer is yes; see the concrete example here.
More generally, but also more technically, suppose that $S$ is some set of finite binary strings. (Any countable set of objects — integers, rational numbers, pairs of integers, etc. — can be coded as a set of such strings.) The nicest sets $S$ are those for which we have efficient decision algorithms: we feed the algorithm a string $s$, and it says yes if $s\in S$ and no if $s\notin S$. Failing that, we might at least hope for an efficient demonstration that $s\in S$ when that is the case, even if — as with the subset sum problem — we can’t efficiently demonstrate a no answer to the question ‘Is $s\in S$?’ Such an efficient demonstration of a yes answer is a certificate (or witness) that $s\in S$.
You’ll find a formal version of this definition in Section $2.3$ of this PDF, together with some explanatory material similar to what I just gave, but more extensive.
If the passage quoted in your question were about the subset sum problem, it would (as I read it) be saying that the algorithm in question checks just one subset $Z$ of $S$ to see whether its sum is $0$ instead of checking all of them.