Electro-Encephalo-Gram basically means "electrical brain graph" (sort of!).
The signals from your brain when it is working appear at the scalp as very small voltages of the order of 10-50 micro-volts (10-50 millionths of a volt). The EEG uses electrodes placed on the scalp to measure these tiny signals, amplifying them about 10,000 times so they can be recorded.
There is a well established methodology for recording these signals, with named positions on the scalp. Check out the Wikipedia entry for EEG for a more detailed description.
With an EEG the machine records the activity at hundreds of samples per second for each electrode on the scalp and normally a trained clinician has to analyse the data and define the sleep stages, which as you can imagine takes a long while for a whole night sleep recording!
There is some research looking at simplifying the EEG to make it easier to diagnose problems such as sleep apnoea or depression, which have particular characteristics in the EEG recording.
Several of the high-profile "dream machines" record brain activity with a simplified EEG, as well as sensing heart rate, movement and temperature, which all fluctuate during the night according to sleep stage.
Did you know that even REM, Rapid Eye Movements, don't occur all the time during a REM phase, i.e. when you are dreaming? Studies suggest about 40% of the time in REM is spent in rapid eye movement.
If you're interested in the technical aspects and want to try experimenting, there is an affordable device available from Olimex called the EEG-SMT. All the data about it is open source, including circuit diagrams (I have no affiliation to them). Check out the Open EEG website as well.