First off, from your question, it is not clear whether or not you understand the "circuit" part. So I'll start there. With (most) FHE schemes, you are evaluating circuits, or a bunch of gates hooked together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by itself is functionally complete. So, with just a single NAND gate, you can construct any circuit. That is why we need a scheme that can compute at least one NAND gate (in addition to its own decryption circuit).
As you stated, FHE schemes add noise to the ciphertext. So, you can evaluate a circuit on the input ciphertext(s), but you may add so much noise in the process of doing this that you can no longer decrypt. That is the problem we are faced with. It is important to remember that inputs to the circuits are ciphertexts, and that the output of the circuit is a ciphertext.
What Gentry gave us what a somewhat homomorphic encryption scheme. After evaluating too many gates, the noise becomes too much and we can no longer decrypt. But, he showed that by taking the decryption algorithm for his scheme and converting it into a circuit and passing the circuit a ciphertext and an encrypted version of the private key, what you would get out was a ciphertext of the same plaintext, but with the noise gone. Furthermore, the cipher allowed you to run at least one NAND gate on two ciphertexts (a couple of gates that were equivalent to a NAND) and the decryption circuit without the noise being too much.
So, let's say we can execute one NAND gate and the decryption circuit homomorphically and still be okay noise-wise. Given a circuit like this
(A NAND B) NAND (C NAND (D NAND A)) we would actually execute it as (say
DEC is the decryption circuit using an encrypted version of the private key):
A NAND B
DEC(D NAND A)
So after every
NAND you would insert a
DEC to eliminate the noise. I should note that even though the last thing you evaluate is
DEC, the value that comes out is encrypted.