At the very least a good course in discrete mathematics is a good start (it's also a good start for anything technical as well - one of the most valuable math classes anyone can ever take, as far as I'm concerned)
Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under complimentation" means), pumping lemma, diagnalization proofs, halting problem. The incompleteness theorem is intimately tied to this. This is the "CS-route" to getting a good understanding in Incompleteness, I'm sure math or physics majors come to approach it in each their own way.
Being a little blunt, a background in philosophy (whether it's academic or not) without a solid discrete math background, doesn't help you out at all. This isn't philosophy, it's just a fact about properties of formal systems of sufficient complexity. If you're looking for philosophy you won't find anything too deep in the proof of Incompleteness. The philosophical implications are not clear.
However, I do recommend Rebecca Goldstein's book. It's not technical, and she's a Princeton philosopher who will indulge you with possible philosophical ramifications of the theorem (along with a good narrative). I also recommend her other books as well, especially her first novella "The Mind-Body Problem". From a philosophical perspective, the dispute between Goedel and Wittgenstein who never accepted the Incompleteness Theorem "whereof we cannot speak we must pass over in silence", which, ironically, speaks of something of which we cannot speak.
> At the very least a good course in discrete mathematics is a good start
I believe that the best starting point to get to incompleteness is formal logic. This is the basic set of concepts that lets us make terms, statements and finally proofs the subject of formal mathematical study, thus tying the loop (formally mathematically defined reasoning about formally mathematically defined reasoning :-) ) that leads to Goedels proof.
Discrete mathematics is helpful but it is rather low level, the core concepts in incompleteness come from formal logic.
Knowing computer science stuff like regular languages is really not required to understand the incompleteness theorems; grasping first order logic, a little arithmetic and some elementary recursion theory is sufficient.
I repeat my objection to the Goldstein book raised elsewhere in this discussion.
Following that, a good class in the theory of computing: understanding what exactly a generative grammar is, properties of classes of languages (e.g., understanding what "regular languages are closed under complimentation" means), pumping lemma, diagnalization proofs, halting problem. The incompleteness theorem is intimately tied to this. This is the "CS-route" to getting a good understanding in Incompleteness, I'm sure math or physics majors come to approach it in each their own way.
Being a little blunt, a background in philosophy (whether it's academic or not) without a solid discrete math background, doesn't help you out at all. This isn't philosophy, it's just a fact about properties of formal systems of sufficient complexity. If you're looking for philosophy you won't find anything too deep in the proof of Incompleteness. The philosophical implications are not clear.
However, I do recommend Rebecca Goldstein's book. It's not technical, and she's a Princeton philosopher who will indulge you with possible philosophical ramifications of the theorem (along with a good narrative). I also recommend her other books as well, especially her first novella "The Mind-Body Problem". From a philosophical perspective, the dispute between Goedel and Wittgenstein who never accepted the Incompleteness Theorem "whereof we cannot speak we must pass over in silence", which, ironically, speaks of something of which we cannot speak.