If $\Gamma$ is consistent and $\Gamma\not\vdash\phi$, then $\Gamma\cup\{\neg\phi\}$ is also consistent. Why?
I came across a solution while writing the question when the key word Deduction Theorem popped up in the side bar. This was not as trivial (for me) as initially assumed. So I decided to give a self-answer, but I am open for answers which show that this may be far more obvious. Especially the "by definition" part in the mentioned answer seems to me like an over-simplification now.
The Deduction Theorem states
If $\Gamma\cup\{\phi\}\vdash\psi$, then $\Gamma\vdash \phi\to\psi$.
Using this result, we can justify the deduction in question.
Assume $\Gamma\cup\{\neg\phi\}$ is inconsistent and therefore proves $\phi$. The Deduction Theorem gives that we can conclude $\Gamma\vdash \neg\phi\to\phi$. This latter statement is equivalent to $\phi\lor\phi$ $-$ or simply $\phi$. So there is a proof of $\phi$ from $\Gamma$ alone. $\;\square$
Please note that you are asking two different questions here.
At some point you ask why you wouldn't be able to deduce $\phi$ when adding $\neg \phi$ to $\Gamma$...and how the author of the post you are referring to shows that 'by definition'. Well, the definition used here is that a set of statements is consistent if and only there is no statement such that that statement as well as the negation of that statement can be derived from that set of statements. Hence, since it is obvious that $\neg \phi$ can be derived from $\Gamma \cup \{ \neg \phi \}$, then the consistency of $\Gamma \cup \{ \neg \phi \}$ implies that $\phi$ cannot be derived from $\Gamma \cup \{ \neg \phi \}$, let alone from $\Gamma$ alone.
Ok, but note that the latter result is the converse of what you ask earlier in your post, and what you ask of in the title of your post and, for that matter, what the author should have argued for, which is that if $\Gamma \not \vdash \phi$ then $\Gamma \cup \{ \neg \phi \}$ is consistent. Indeed, it is likely that you are confused about the Answer you are referring to since it is in fact not a good answer to the question that was asked there. Ok, so then how do you show what needs to be shown? Well, see the answer by @M.Winter for one good answer!
Note that the above argument use nonconstructive law of reductio ad absurdum:
Let $X\cup\{\neg\varphi\}$ be an inconsistent set of formulas. Then $X\cup\{\neg\varphi\}\vdash\varphi $, so Deduction Theorem gives: $X\vdash\neg\varphi\rightarrow\varphi $. But reductio ad absurdum $(\neg\varphi\rightarrow\varphi)\rightarrow \varphi $ is clasically valid, so by Modus Ponens, $X\vdash\varphi $. $\blacksquare$
This theorem is not true in Intuitionistic Logic. Indeed, $\not\vdash_{INT}p\vee\neg p$, but $\{\neg(p\vee\neg p)\}$ is inconsistent:
suppose that there is a finite Kripke model $K$, and a world $x\in K$, such that $x\Vdash \neg(p\vee\neg p)$. Then taking a maximal element $y$ over $x$, we have $y\not\Vdash p\vee\neg p$, which is mpossible. $\blacksquare$
In Intuitionistic Logic the weaker form holds: If $X\cup\{\varphi\}$ is inconsistent, then $X\vdash_{INT}\neg\varphi $.