I just spent an hour trying to figure this out, AGAIN! To compile Zlib support into your Python interpreter, do this:

1. Install the Zlib-dev package for your distribution. (you probably have zlib already, but not the dev package)
On Ubuntu it’s called ‘zlib1g-dev’, on others it might just be: zlib-dev or zlib-devel. Do a search on your distro package lists to find it.
You should end up with a ‘zlib.h’ file in your system. In mine, Ubuntu, I have /usr/include/zlib.h

2. Get your python sources to compile and run the configure script like so:
./configure –with-zlib=/usr/include

See there that I included the ‘/usr/include’ directory to find zlib.h in? After the make && make install it worked great!

Keep in mind your mileage may vary, but this might help I hope. More importantly, now I can remember how I did this! :)