User's solution

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.