By far the most important step for recording decent signals is to make proper electrical contact with the skin. If you don't take this statement seriously, you are likely to get nowhere. Especially for EEG. Just putting bare metal on the skin doesn’t make an adequate connection. The skin must be prepared, and an electrolyte—a conductive interface—is needed, along with a metal electrode. Electrolytes and metal electrodes in turn are the basic components of batteries—a property which can cause serious trouble. If the metal-electrolyte interface is in any way different at the two active electrodes, their "half cell" potentials will be different, resulting in a small DC offset. An offset of only 100 mV (which is puny by battery standards) when multiplied by a gain of 50 gives 5 volts. Since the AD 620 output cannot exceed the 2.5 - 4.5 volts positive or negative provided by the Arduino or the batteries (in reality, it won't even get that far), the amplifier will lock up, and the output will be a flat line. A bit of corrosion on the electrodes, or different electrolyte mixtures/different metals on different electrodes, can be enough to cause this.
Equally annoying is the 60-Hz electric field that permeates all of our bodies in electrified environments. This can easily exceed 0.1 volt. (Yes, that's about 2000 times larger than the EEG.) Instrumentation amplifiers like the AD 620 are optimized to reject this "common mode" artifact, which is about the same on different parts of the body. However, large and unequal electrode impedances will cause 60-Hz noise to sneak in and swamp the signal.
(It might be possible to get by with lousier skin connections using active instrumentation amplifiers with feedback to the neutral electrode. Such amplifiers are often labeled by their original usage in EKG as "driven right leg." However, they won't fix DC offsets, are more complicated, and in my experience are flakier than the simple passive amplifiers described here.)
Even after initial amplification, the EEG is so tiny that 60-Hz noise can be picked up from the preamp circuitry. The preamp gain of around 20 - 50 therefore represents a compromise between the need to get the signal up out of the noise as soon as possible while minimizing the perils of DC offset from the electrodes. The use of microphone cable or a twisted wire pair from the preamp to the audio jack helps to reduce additional 60 Hz pickup on the way to the computer.
Professional neurophysiologic recording is done with fancy electrodes made of gold or silver/silver chloride. The skin is often rubbed with fine suspensions of abrasives and EEG electrodes are glued on with specially-formulated sticky electrolytes. These items are generally unavailable to amateurs. However, if you happen to have a contact at a hospital or neurologist's office, I suggest you use it and get some commercial EEG paste. Usable alternatives are brass, very fine sandpaper, rubbing alcohol, and K-Y jelly thickened with flour. (Copper is widely available in the form of US pennies, but is very vulnerable to corrosion from electrolytes.) Prepare the skin by rubbing gently with the sandpaper, and then wipe it with alcohol and allow it to dry. Mix a cc of K-Y jelly with flour until it is the consistency of Play-Doh, and then scoop up a thick dab of it on each electrode.
Electrodes on the hands and arms can be taped in place for additional security, and you can get by with K-Y jelly alone. EKG and scalp electrodes are a problem, making the combination of K-Y jelly and flour more useful. The electrode and wire lead should be light and thin so that their weight and stiffness doesn't pull them off the head. I used thin, 1/2 in wide brass strips from Ace hardware, cut into octagons 1/2 in across. The leads were 26-gauge multistrand wire peeled from a connector strip and soldered to the back of the brass electrodes. (You DO NOT need thick electrodes, thick wire, shielded wire, or heavy insulation. Magnet wire would do fine except for the tendency to break with repeated use.) The active face of the electrode should be washed and polished gently before each use, to remove corrosion and polarization. The solder joint should not be part of the electrode-scalp interface. I cover it with epoxy.
When you are done for the day, soak the electrodes and clean off all the electrolyte before you put them away.