Let me phrase the argument in somewhat more modern terms:
Goedel constructs a means of encoding any computer program's source code by an arithmetic formula, such that he can prove that, for any program which eventually outputs "YES", Peano Arithmetic (PA) proves the corresponding formula, and for any program which eventually outputs "NO", PA disproves the corresponding formula.
Then Goedel* constructs a computer program with the code "Search through all the possible proofs in PA till you find either a proof or a disproof of the formula corresponding to my source code. If you find a proof first, output 'NO'; if you find a disproof first, output 'YES'. (If you never find either, just keep on searching forever...)" [This is a recursively defined program, in that it refers to its own source code, but that's ok: we understand well how to write up such recursive programs, and even how to compile them to languages that do not directly support recursion. This compilation is essentially what "diagonalization" does]
Now, let p be the formula corresponding to this program's source code. So long as PA either proves or disproves p, this program will eventually output something. But if this program outputs 'YES', then PA must prove p (by the second paragraph) and also disprove p (this is the only way the program ever outputs 'YES'). Similarly, if this program outputs 'NO', then PA must disprove p (by the second paragraph) and also prove p (this is the only way the program ever outputs 'NO'). Thus, if PA either proves p OR disproves p, it necessarily proves p AND disproves p; they're a package deal. So if PA is "complete", then it is inconsistent.
That is the mechanism of the result. It's quite concrete and doesn't depend on any handwavy arguments about meta-statements. It's just a matter of A) knowing how to construct computer programs which can access their own source code, and B) having an appropriate representation of such programs in PA (or whatever system one is interested in), in the sense of the properties of the second paragraph of this post.
[*: I say Goedel, but I actually mean Rosser, five years later; I've chosen to use his approach (which yields a slightly stronger result than Goedel in this context, albeit one which generalizes less) because I think it might be simpler to discuss for now]
Is it possible to deduce Godel's first incompleteness theorem from Chaitin's incompleteness theorem?
Gödel's incompleteness theorem, in its modern form using Rosser's trick, only requires that (beyond being effective and sufficiently strong), the theory must be consistent. There is no requirement that the theory has to be $\omega$-consistent or meet any soundness assumption beyond simple consistency. You cannot apply Chaitin's theorem in its usual form to these theories, in general, because the usual form of Chaitin's theorem assumes more (e.g. many proofs of Chaitin's theorem assume as an extra soundness assumption that the theory only proves true statements.)
Many of the "alternate proofs" also require stronger assumptions than the standard proof of the incompleteness theorem. You have to be very careful when reading about this to check which assumptions are included in each theorem.
In the particular proof of Chaitin's theorem presented by Kritchman and Raz, however, they do not need to assume any particular soundness beyond just consistency. I am going to explain this in detail.
They do need to assume that $T$ is sufficiently strong. In particular, they assume that if $n$ and $L$ satisfy $K(n) < L$, then $T \vdash \hat K(\dot n) < \dot L$. Here $\dot n$ and $\dot L$ are terms of the form $1 + 1 + \cdots + 1$ corresponding to $n$ and $L$, and $\hat K$ is a formula of arithmetic defined directly from the definition of $K$. (Note that the set of pairs $(n,L)$ with $K(n) < L$ is recursively enumerable, so there is no real issue in assuming $T$ proves all true sentences of that form.)
Given the assumption on $T$, their proof goes as follows (rephrased in more precise terms):
Begin proof
Given $L$, we can make a program $e_L$ that does the following:
Search for any $n$ such that $T \vdash \hat K (\dot n) > \dot L$. We do this by searching through all $T$-proofs in an exhaustive manner.
Output the first such $n$ we find, if we ever find one.
Because we can code $L$ into the program as a fixed constant, using the standard coding methods, the length $|e_L|$ of $e_L$ no worse than $2\log(L) + C$ for some constant $C$. In particular, we can fix an $L$ with $|e_L| < L$. Assume such an $L$ is fixed.
For this $L$, suppose $e_L$ returns a value, $n$. Then $K(n) \leq |e_L| < L$. By our assumption that $T$ is sufficiently strong, this means $T$ proves $\hat K (\dot n) < \dot L$.
But if $e_L$ returns $n$ then $T$ also proves $\hat K(\dot n) > \dot L$. This means that if $e_L$ returns a value then $T$ is inconsistent. So, if we assume $T$ is consistent, then $e_L$ cannot return a value. This means that, for our fixed $L= L_T$, $T$ cannot prove $\hat K(\dot n) > \dot L$ for any $n$.
Thus, if we take $n = n_T$ to be such that $K(n) > L$, we have that $\hat K (\dot n) > \dot L$ is a true statement that is not provable in $T$.
End proof
This proof just given (in italics) proves:
If $T$ is a consistent, effective theory of arithmetic that proves every true formula of the form $\hat K(\dot n) < \dot L$, then there is a true statement of the form $\hat K(\dot n) > \dot L$ that is not provable in $T$.
This is almost the same as Gödel's incompleteness theorem. The only difference is that the usual proof of the incompleteness theorem gives us an explicit formula that it is true but not provable in $T$ (namely, the Rosser sentence of $T$). On the other hand, the proof in italics requires us to find $n_T$ in order to have an explicit example, and there is no algorithm to do this.
This is one motivation for what I think of as the "standard form" of Chaitin's theorem. In that form, we look instead for unprovable sentences of the form ($\dagger$): $(\exists x)[\hat K(x) > \dot L]$.
Because we can compute $L= L_T$, we can compute a specific sentence of that form for $T$. But, for the proof to work, we need to have an actual $n$ such that $T \vdash \hat K(\dot n) > \dot L$. So we have to add an additional soundness assumption to the theorem, namely that if $T$ proves a sentence of the form ($\dagger$) then there is an $n$ such that $T$ proves $\hat K(\dot n) > \dot L$.
Overall, in this version of Chaitin's theorem, we have an explicit sentence, but with a stronger soundness assumption. The proof of Gödel's incompleteness theorem using Rosser's method gives us an explicit sentence without any stronger soundness assumption.
Best Answer
Godel produces a sentence $\varphi$. What Godel proves is that - assuming $PA$ is consistent - $\varphi$ is true but not provable in $PA$. (I'm assuming the theory we're looking at is "PA," here - but we can of course replace $PA$ with any sufficiently strong recursively axiomatized theory, such as PM, ZFC, NF, ...)
This proof goes through perfectly inside the theory $PA$. There's no contradiction, though, because - in order to conclude that $\varphi$ is true - $PA$ would have to know that $PA$ is consistent. So, instead of a paradox, we get Godel's second incompleteness theorem: that, if $PA$ is consistent, $PA$ doesn't prove "$PA$ is consistent."
I'm being ahistorical here - in fact, what Godel proved was slightly weaker, and Rosser was the one who brought the hypothesis down to "$PA$ is consistent" - but this is the meat of the situation.