This caused an unnecessary headache.

Follow the official docs to set up the Elastic Beanstalk CLI tools. The step I missed was:

"If your Linux distribution came with Python, you may need to install the Python developer package in order to get the headers and libraries required to compile extensions and install the EB CLI. Install the developer package (typically named python-dev or python-devel) using your package manager."

If you manage to forget to do this then this happens on Amazon Linux AMI release 2016.03:

pip install awsebcli 

...
ext/_yaml.c:8:22: fatal error: pyconfig.h: No such file or directory
 #include "pyconfig.h"
                      ^
compilation terminated.
error: command 'gcc' failed with exit status 1

----------------------------------------
Failed building wheel for pyyaml
Running setup.py clean for pyyaml
Failed to build pyyaml
Installing collected packages: pyyaml
Running setup.py install for pyyaml ... error
...

something.h: No such file or directory normally means "install header files" :) which are in this package:

yum install python27-devel

which fixes the issue.