There are a number of different methods of implementing a brain computer interface. The first major division in approaches is whether the BCI is invasive or non-invasive. In this context, "invasive" means that a surgeon cuts open you head, saws open your skull, and implants electrodes directly in your brain. If you're a quadriplegic, you might be willing to have this done in order to get your best chance at a BCI that works well.
For the rest of us, though, we might be more interested in a non-invasive BCIs that sense your brain waves by electrodes on the scalp.
How do BCIs listen to the signals from your brain (via your scalp) and do something useful? To my understanding there are three approaches: Frequency Analysis, Mu Wave Detection, and Event-Related Potentials.
The simplest approach is simply to look at the frequency content of the EEG signals recorded from the scalp. Since nearly everyone produces alpha waves when they close their eyes, a straight-forward example of a frequency-based BCI would be to program the computer to move a motor in proportion to the alpha waves measured in the EEG signals. I've done it. It's fun! More complex control schemes can be developed by looking at more frequency bands (theta, alpha, beta, etc) and by looking at different or multiple locations on the scalp. With this added range of variables, you can do more complex things. The video below shows an example of this kind of setup.
The hard part is that most people cannot easily control the frequency content of the signals in their head. Usually, you're asked to control wishy-washy aspects of your mental/emotional state such as "alertness", "relaxation", "focus", etc. How do you do that? Well, it requires much practice and, to date, has yielded unreliable results for most people. But, it is easy to implement on the computer, so it's a good starting place for people hacking their own BCI system.
Mu Waves (Mu Rhythms)
A special case of the "Frequency Analysis" methods is a method based on looking for "Mu Waves". Mu waves are special because they occur in the motor cortex (or, more precisely, in the combined sensorimotor cortex). If you can get your scalp electrodes in the right place, you will see Mu waves whenever your body is physically relaxed. When you contract the muscles in a relevant body part (or, even if you just visualize yourself contracting the body part), the Mu waves in that part of your brain get suppressed. So, the EEG setup is a little harder, but one's ability to actually control these brain waves is much better.
To get more information on how to do a Mu wave BCI, the BCI2000 folks have some great information
For another example, check out the video below. They built a BCI for playing World of Warcraft. If you skip to 0:46, you see how they put together the system and how, through the subject moving his feet and hands, they trained the computer to understand his brain waves. This use of physical motions is almost certainly training the system to look for the subject's Mu waves. Furthermore, note that the only electrodes that are wired-up on his EEG cap are the ones over his motor cortex. It's gotta be a mu-wave system.
Follow Up: Here's more discussion of using Mu waves for my BCI.
Event-Related Potential (ERP)
A third way to do a BCI is to measure event-related potentials (ERPs). ERPs are EEG measurements in response to a particular sensory stimulus, which then causes a particular response in the brain. Often visual stimuli are used via a computer screen. This is useful for BCI because, if the user is consciously paying attention to the visual stimuli, his brain gives one type of response (that is detectable via EEG), while if he ignores the stimuli, it gives a different response. This means that the human subject can consciously interact with the computer simply through selectively focusing (or not) on the visual stimuli.
The video below presents a typical setup. Here, the computer presents a grid of letters on the screen. The human subject wants to spell a word, so he focuses his attention on a letter on the screen...the letter "S", for example. The computer then randomly highlights the letters on the computer screen. Whenever the letter "S" is highlighted, the human recognizes that his letter was highlighted and his cognitive response causes a quick and temporary change in his EEG signals (the "P300" feature appears). Unfortunately, the P300 is a very subtle change, so the whole process has to be repeated many times so that the recordings can be averaged together to make the P300 detectable. If the computer has to flash through the whole keyboard, you can imagine how slow this is. The video below illustrates the slowness...he gets about one letter every 40 seconds.
Still, even though it is slow, ERP interfaces allow for a very rich interaction with the computer that can be more complex than the simple "left", "right", "forward" commands seen in the World of Warcraft video above. Plus, the system used in the video is not the be-all and end-all in ERP interfaces. This is a very new field and many advances are possible.
If you want to learn more about (or try!) a P300 ERP system, the BCI2000 folks also have some tutorials: