I was using Fedora 6 (Linux) and my Python wasn't compiled with zlib support. It was painfully frustrating to figure out what was required, but I did this:
yum install zlib
yum install zlib-devel
and then a "./configure" (with --enabled-shared for my case), a "make clean", and then a "make" built the proper zlib module. Supposedly Python comes with its own zlib code, but it doesn't seem to trigger properly.
Once I did this compile, I saw that zlib.so was produced for the zlib module. I suspect for most people a "make install" would help to get it into the right place.
Comments
I saw a similar error using python 2.6 on Centos 5.2. To fix I ran yum install zlib-devel and then ran make from within python directory. Problem solved!
Unfortunately the solution is to manually re-compile your Python from source after installing the relevant zlib-devel libraries with Yum.