Note: Since a while back, there are binary wheels for Windows in PyPI, so this should no longer be an issue for Windows users. Below are solutions for Linux, Mac users, since lots of them find this post through web searches.

Option 1

Install the psycopg2-binary PyPI package instead, it has Python wheels for Linux and Mac OS.

pip install psycopg2-binary

Option 2

Install the prerequsisites for building the psycopg2 package from source:

Debian/Ubuntu

Python 3

sudo apt install libpq-dev python3-dev

You might need to install python3.8-dev or similar for e.g. Python 3.8.

Python 2¹

sudo apt install libpq-dev python-dev

If that's not enough, try

sudo apt install build-essential

or

sudo apt install postgresql-server-dev-all

as well before installing psycopg2 again.

CentOS 6

See Banjer's answer

¹ Really? It's 2021

On CentOS, you need the postgres dev packages:

sudo yum install python-devel postgresql-devel

That was the solution on CentOS 6 at least.

On Mac Mavericks with Postgres.app version 9.3.2.0 RC2 I needed to use the following code after installing Postgres:

sudo PATH=$PATH:/Applications/Postgres.app/Contents/Versions/9.3/bin pip install psycopg2