First let me try to state in clear terms exactly what he proved, since some of us may have sort of a fuzzy idea of his proof, or have heard it from someone with a fuzzy idea of the proof..
The proof begins with Godel defining a simple symbolic system. He has the concept of a variables, the concept of a statement, and the format of a proof as a series of statements, reducing the formula that is being proven back to a postulate by legal manipulations. Godel only need define a system complex enough to do arithmetic for his proof to hold.
Godel then points out that the following statement is a part of the system: a statement P which states "there is no proof of P". If P is true, there is no proof of it. If P is false, there is a proof that P is true, which is a contradiction. Therefore it cannot be determined within the system whether P is true.
As I see it, this is essentially the "Liar's Paradox" generalized for all symbolic systems. For those of you unfamiliar with that phrase, I mean the standard "riddle" of a man walking up to you and saying "I am lying". The same paradox emerges. This is exactly what we should expect, since language itself is a symbolic system.
Godel's proof is designed to emphasize that the statement P is *necessarily* a part of the system, not something arbitrary that someone dreamed up. Godel actually numbers all possible proofs and statements in the system by listing them lexigraphically. After showing the existence of that first "Godel" statement, Godel goes on to prove that there are an infinite number of Godel statements in the system, and that even if these were enumerated very carefully and added to the postulates of the system, more Godel statements would arise. This goes on infinitely, showing that there is no way to get around Godel-format statements: all symbolic systems will contain them.
Your typical frustrated mathematician will now try to say something about Godel statements being irrelevant and not really a part of mathematics, since they don't directly have to do with numbers... justification that might as well turn the mathematician into an engineer. If we are pushing for some kind of "purity of knowledge", Godel's proof is absolutely pertinent.
In addition, some known mathematical phenoma already exhibit the Godel incompleteness property. For instance, in set theory mathematicians define different degrees of infinity based on the number of members of the set of all integers, rational numbers or reals. The first degree of infinity, called (aleph-nought), is the number of integers or the number of rational numbers (these numbers are the same "degree of infinity"). The second degree of infinity is aleph-nought raised to the power aleph-nought. For a long time people were trying to decide whether 'C', the number of real numbers, was the same as the second degree of infinity. Finally it was proven that whether C and 2nd infinity were equivalent came down to the truth or falsehood of a statement that could not be proven from the existing axioms of mathmatics. This statement was absorbed as a new axiom, just as Godel statements would have to be. So there is the first of many Godel-style statements that we'll probably see popping up in mathematics.
Of course, a more familiar example is the parallel-postulate axiom, since it cannot be proven from any other axioms of Euclidean geometry, and in this case the way you define it leads to at least three different self-consistent systems.
In any case, what does it mean that a symbolic system based on deriving truth from axioms is incomplete? Could we make a complete system? The only way I can see to do that would be to include an infinite number of axioms, which deterministicly describe all happenings in the past, present and future. This would only work in a deterministic universe, and it would be difficult to draw a distinction between the data of this 'complete' system and reality itself.
Thinking of the data required is perhaps the right direction to move in: it is the reason the symbolic system is incomplete. The symbolic systems we use to describe the universe are not separate from the universe: they are a part of the universe just as we are a part of the universe. Since we are within the system, our small understandings are 'the system modelling itself' (system meaning reality in this case). Completion of the model can never happen because of the basic self-referential paradox: the model is within the universe, so in effect the universe would have to be larger than itself. Or you can view it iteratively: the model models the universe. The universe includes the model. The model must model itself. The model must model the model of itself.. ad absurdum.
So Godel's incompleteness is something to expect. It is even something that can be intuitively understood without a mathematical approach and proof: the incompleteness concept appears in clearly recognizable form in Zen Buddhism.
So it brings to mind how to solve the paradox. There is the idea that consciousness might be a kind of superset of the universe, and thus through consciousness we might understand the universe. Yet we must realize that consciousness and the universe represent a yet larger system or universe to "understand" ( if that word still applies ). This continues iteratively as well.
We can perhaps move beyond the self-referential part of the paradox by moving beyond the self: becoming through some higher dimensionality or level of complexity something with no coherant self, or clear perception- point.
The Zen answer to what to do next is that real truth is in everyday life. This may well be so: in a universe where knowledge defeats us, what can we do but be what we are? We have to ask why it is that it matters that knowledge of the universe be moved into symbolic representation in our minds. The information we seek is in existence around us at all times, happening in the patterns we seek to understand and quantify. What good is there in this understanding? Clearly we are evolutionarily driven to this attempted understanding, but is there a better reason to be had?