What are the requirements to understand Gödel's Incompleteness Theorems?

My familiarity with the theorem is mostly from Douglas Hofstadter’s book, Godel, Escher, Bach

The book gets a little too cute at times, but for the most part I enjoyed it. According to Hofstadter, most of the difficulty in the theorem comes from setting up the machinery for manipuating logical statements using arithmetic. What this book does is to assume the existence of this machinery and to provide a high level view of how it is used to prove the theorem. I recommend the book as a good introduction. I can’t help you much if you want to get into the low level details.

The actual mathematics required is relatively simple—elementary number theory and primitive recursion. A greater obstacle is the formal logic; in order to grasp what Godel is doing, one must be familiar with some of the low level mechanics of formal derivations. In particular, it is crucial to understand freedom and bondage of variables and the notion of substituting a term for a variable in a formula. Godel’s paper probably isn’t the best place to start because the logical system and the notation he uses are seldom used today and his German mnemonics have been retained in the translation, so that it is difficult to find references for portions that prove hard to grasp.

The authoritative translation is found in the first volume of Godel’s Collected Works, where it is accompanied by expert commentaries. There is a translation by Martin Hirzel that attempts to incorporate modern terminology and English mnemonics.

Melvin Fitting’s Incompleteness in the Land of Sets presents the proof in the context of finite set theory, which simplifies the encoding.

I second @LostInParadise‘s vote for Hofstadter, who explains recursive self-reference like no other. Too cute? You mean like pushcorn or meta-genies? The dialogues? I’d say he’s being witty, clever, & entertainingly informative but not overdone. At times he uncannily anticipates a question or point of confusion and explains it in the next sentence. You can see I’m a big fan of Douglas Hofstadter’s writings.

I forgot to add “lol” to previous, lol.

I’d been racking my brain to remember where I recently saw a new explanation of Godel numbering based & proof of the theorem. It’s in James Gleick’s The Information. Quite readable and much shorter than Hofstadter, Gleick gives you the gist of it.

I’d say the only mathematical prerequisite is to understand symbolic logic and the concepts of prime numbers and factorization.