I'll give a simplified version of Penrose's reasoning.
In a sense this goes back to the "liar paradox" that has been known for thousands of years. Suppose I say "I'm lying"; then that should mean that I am telling the truth; but that would mean that I am lying. Statements that refer to themselves, or which refer to each other in circles, can create unresolvable contradictions.
Analogous paradoxes can be constructed for mathematics and computation.
You can have a computer program which predicts whether another computer program will eventually stop running, or run forever; and then it has a nemesis program which contains a copy of the prediction program and always does the opposite of what it predicts. The prediction program inherently cannot win. Either it makes no prediction, or it makes the wrong prediction.
Godel did something similar for a theorem-proving program. He was able to encode how the program works in arithmetic, and then write down an equation which implies that "The theorem prover says this equation is false". This nemesis sentence of the theorem prover is called the Godel sentence. Either the theorem prover "has no opinion" about whether the Godel sentence is true or false, or it gets caught in contradiction.
This is the incompleteness theorem. If the prover is always correct, it must avoid taking sides on Godel sentences, or else it will fall into contradiction. To remain consistent in its assertions, its power to deduce the truth must be incomplete.
The Godel sentence is possible because ordinary computation can be reduced to arithmetic operations on zeroes and ones, so facts about what a computer can and cannot do, can be expressed in arithmetic. However, you could have a special computer which, in addition to the usual logic gates, has a magic component which correctly outputs the answer to problems like "does this program halt" or "is this Godel sentence true". Mathematically, the magic component computes a function - it takes an input and produces an output - but it is not a function that can be implemented using arithmetic operations. Such a function can be called an oracle function.
Now consider the capacity of the human brain to reason about mathematics, under the assumption that the human brain follows laws of physics. The known laws of physics involve computable functions. One might then conclude that there must be Godel sentences for the human brain too, mathematical statements which, even if true, are beyond the power of human reasoning.
Penrose chose the other option. Human beings can reason correctly about Godel sentences, therefore the human brain must be able to employ oracle functions, and so physics must contain processes which require oracle functions for their definition. His concrete proposal (elaborated with Hameroff) is that human cognition employs quantum entanglement in the brain, and that quantum dynamics (especially the collapse of the wavefunction) is determined by subtle quantum-gravitational effects governed by an oracle-function law.