There is nothing about countability or uncountability in Gödel's proof. All the sets of statements and proofs are assumed to be countable.
There is a logical relationship between what Gödel did and how Cantor showed some sets were "uncountable" - they are both what we call "diagonal arguments." Diagonal arguments crop up in lots of logic, especially when we are talking about the limits of what we can do with formal systems.
The grandfather of the diagonal argument is Russell's paradox. It essentially forces us to realize that we cannot talk about "the collection of everything" in a naive way and not get a paradox. It has a strong relation to the statement, "This statement is false," which clearly cannot be assigned a truth value.
Gödel was able to show that if a (finitely describable) system of axioms was complicated enough to contain arithmetic, then it was complicated enough to talk about proofs in itself, and, in particular, to write a statement that says, "This statement has no proof in the X axiom system." If this statement had a proof, then we'd be able to disprove it, as well. If the statement has no proof, then it is true.
One way to think of it is in terms of something called "computability." The set of provable statements in an axiom system is "recursively enumerable." But if all theorems are decidable by proofs, then the set of provable statements and the set of disprovable statements comprise all statements, and, if the theory is consistent, they are disjoint. A recursively enumerable set whose complement is also r.e. is necessarily "recursive." Gödel essentially proved that this cannot be.
(Note that in computability theory, the distinction between "recursive" and "not recursive" is much like the set theory distinction between "countable" and "uncountable.")