Update: Nowadays installing is done with pip, but libyaml is still required to build the C extension (on mac):
brew install libyaml
python -m pip install pyyaml
Outdated method:
For MacOSX (mavericks), the following seems to work:
brew install libyaml
sudo python -m easy_install pyyaml