I accidentally ran into this old question and thought to give an example whose (humble!) intention is to permanently deconfuse anyone who knows just a little bit of undergraduate mathematics.

Consider group theory. In a typical introductory course, you will learn the simple axioms and immediately encounter sentences like

$$\forall y \forall x \forall z( (xy=e) \wedge (zy=e ) \Rightarrow x=z);$$

or slightly more complicated ones like

$$(\forall x(x^2=e ))\Rightarrow (\forall x\forall y(xy=yx)).$$

You also learn how to deduce them rather easily from the axioms of the theory.

How about the sentence

$$S:\ \ \ \ \ \ \ \forall x \forall y( xy=yx)$$

?

Can it be deduced from the axioms? Obviously not, but it requires at least a bit of thoughtfulness to
prove that it can't. You see, we can just write down a structure like $S_3$ that satisfies the axioms of group theory,
a *model* of group theory, and produce two elements in it for which the sentence is not true. Obviously we couldn't produce
such a model if the sentence was a logical consequence of the axioms.

How then about $\neg S$? Can it be deduced from the axioms? Again obviously not. Consider the integers $Z$.

So we see that group theory is incomplete: We've written down a sentence $S$ such that neither $S$ nor $\neg S$ can be
deduced from the axioms.

But here is an important point: If the context of the discussion was the group $Z$, is the sentence $S$ true? Yes, of course, and I can prove it for you. (Using more than the axioms of group theory, of course.)

For a complete theory, every true assertion $S$ (in the language of the theory) about a given model $G$ can be deduced from the axioms. This is because $S$ or $\neg S$ can be deduced,
but if $\neg S$ could be deduced, then it would have to be true in any model of the theory, in particular, $G$. So $S$ would be
false in $G$. But $S$ is true. Therefore, it must be the one that can be deduced. The upshot is that whenever you have a theory (like group theory) with a model that admits a true sentence that can't be deduced from the axioms, then the theory is incomplete. The point of boring you with this discussion
is to illustrate that an incomplete theory is a very mundane object.

In case this suggests (as it should) that a complete theory, on the other hand, is bound to be very exotic, you might like this
simple list of a few complete theories.
For example, the theory of algebraically closed fields of characteristic zero is complete. This implies, in particular,
a logical incarnation of the 'Lefschetz principle': A field-theoretic sentence true in $C $ is true in every algebraically
closed field of characteristic zero. In fact, as noted above, a sentence true in any given model, since it can be deduced from the axioms,
is true in any other model. I found this fact quite mind-boggling when I first encountered it. A good exercise is to see why a sentence like 'every element of $\bar{Q}$ is algebraic' doesn't cause a problem. (You need to get a bit more precise to do this, especially about the language of the theory.)

There is a complete theory of the natural numbers, by the way. Add to your favorite axioms of
arithmetic *all the sentences that are true in the natural numbers*. This is a perfectly respectable complete theory, sometimes referred to as the *theory of natural numbers*. Goedel's first incompleteness theorem can be
interpreted as saying this theory doesn't admit a recursively enumerable set of axioms. (Which should be at least
intuitively plausible if you consider difficult unresolved problems like, say, Goldbach's conjecture.)

Added:

In my opinion, it's not such a good idea to emphasize the 'string of formal symbols and rules' point of view when explaining the incompleteness theorem. It's true that to *prove* the theorem, you need to set up such background formalities. But the statement itself can plausibly be interpreted as something about everyday reasoning in mathematics. We are usually interested in some structure, a rather specific one like $Z/2$, a somewhat more general one like 2-groups, or more general yet like all groups. The question concerns which properties (or axioms satisfied by the structure, if you prefer) we use to prove certain assertions. The everyday nature of this question was the reason for bringing up the commutativity of $Z$, which I can certainly prove in the course of a normal discussion on the chalkboard, but anyone can see requires more than group theory.

This question also comes up rather frequently as one of great interest to practicing mathematicians. An advanced example that I can remember off the top of my head is 'Can one prove the Kodaira vanishing theorem using only algebraic geometry?,' which was resolved first by Faltings (although there is room for interpretation of the phrase 'only algebraic geometry').

In some sense, the rationale for the abstract formalism surrounding the incompleteness theorem is also pretty commonsensical. To prove that something *can* be done, you just need to do it. For example, I think it is uncontroversial that the proof of the Kodaira vanishing theorem by Deligne and Illusie uses 'only algebraic geometry.' And then, there are the famous elementary proofs of the prime number theorem. To prove that something *can't* be done, on the other hand, often requires more careful foundations.

Added again:

After some conversations, I decided to put in a few final words of clarification. I hope I didn't slight anyone with the joke about 'permanent deconfusion.' I don't claim to have any serious understanding of philosophical ramifications, for example. However, I tried to articulate what seems to me a sensible view of the matter for *practicing mathematicians*. Starting from the one given, you can yourself quickly make up examples illustrating the (uninteresting) incompleteness of a large majority of the theories we usually work with, rings, fields, topological spaces, etc. After that process, and thinking through just the few implications of completeness already mentioned, if someone came up to you and claimed that Peano Arithmetic was complete, I suspect your eyes would pop out.

Someone once told me that a good way to sound sophisticated as an amateur logician is to proclaim that the completeness theorem* is much more important than the incompleteness theorem. That's perhaps too sweeping a statement, but it seems to be the one that's useful for usual mathematics. For people interested in pursuing this line of thought, I recommend the nice lectures delivered by Angus Macintyre at the Arizona Winter School in 2003:

http://math.arizona.edu/~swc/aws/03/03Notes.html

One intriguing observation there I sometimes think about is how number-theoretic completions (reals and $p$-adics) correlate to logically complete theories.

*The completeness theorem essentially says that a sentence is a logical consequence of the axioms *if and only if* it's true in all models of the axioms. The idea for the non-trivial direction is to show how to construct, given any sentence that can't be deduced, a model for the axioms in which it is false.