GSR

+ very handy to use
- places demands on the quality of the circuitry

EMG

+ cheap (around $10 excluding the breadboard and the batteries)
+ detection of REM possibly fairly easy
- setting up electrodes is a bit of a hassle

A very simple EMG circuit which might still be sufficient for our purposes. It outputs to a microphone input. It needs some custom code which I haven't looked for yet.

http://pni.unibe.ch/Chip.htm