This is one of those posts I'm making for future reference because I always forget.
If you've built Ruby with Visual Studio (instead of using the mingw32 stuff), you'll need to build zlib from source. You could use the pr-zlib library, but it's slower and you'll need to install it in a non-conventional manner. Anyway, under the zlib-x.y.z/contrib/vstudio directory, look for the subdirectory that matches your version of Visual Studio, e.g. "vc10". You'll see a solution file (.sln) file there. Open that solution in Visual Studio.
You should see several projects in that solution. Remove them all except "zlibvc", as it's the only one you'll need. Before you build it, you'll need to remove the ZLIB_WINAPI preprocessor definition (under Project -> Properties -> Configuration Properties -> C/C++ -> Preprocessor, on Visual Studio 10 anyway). Once that's done, build your solution. It will generate some files in zlib-x.y.z/contrib/vstudio/vc10/x86/zlibdlldebug. Look for the .dll and .lib files, and put them someplace sane, like c:/usr/lib. I also copy all the .h files to c:/usr/include. You may also need to copy the .dll file to the c:/ruby/bin directory.
Once those files are in place, cd back to your Ruby source directory under ruby-x.y.x/ext/zlib, and run "ruby extconf.rb --with-zlib-dir=c:/usr; nmake; nmake install", modifying the dir to wherever you put the files. One caveat here is that the zlib folks seem to like to tinker with the zlib output file names. You can either edit the extconf.rb file to make sure it picks them up, or just rename the .dll and .lib files to "zlib.dll" and "zlib.lib", respectively before trying to build it.
Once that's done fire up irb and do "require 'zlib'" to make sure it works.