What version of libz are you using? I tried the one out of my cygwin install, but get this at the end:

C:\Perl5.10\cpan\build\PerlIO-gzip-0.18-dz4dHj>nmake

Microsoft (R) Program Maintenance Utility Version 8.00.50727.762
Copyright (C) Microsoft Corporation.  All rights reserved.

        gcc -c    -DNDEBUG -DWIN32 -D_CONSOLE -DNO_STRICT -DHAVE_DES_F
+CRYPT -DUSE_SITECUSTOMIZE -DPRIVLIB_LAST_IN_INC -DPERL_IMPLICIT_CONTE
+XT -DPERL_I
MPLICIT_SYS -DUSE_PERLIO -DPERL_MSVCRT_READFIX -DHASATTRIBUTE -fno-str
+ict-aliasing -O2    -DVERSION=\"0.18\"  -DXS_VERSION=\"0.18\"  "-IC:\
+Perl5.10\li
b\CORE"  -DLAYERGZIP_DEFAULT_OS_TYPE=11 gzip.c
Running Mkbootstrap for PerlIO::gzip ()
        C:\Perl5.10\bin\perl.exe -MExtUtils::Command -e chmod 644 gzip
+.bs
        C:\Perl5.10\bin\perl.exe -MExtUtils::Mksymlists  -e "Mksymlist
+s('NAME'=>\"PerlIO::gzip\", 'DLBASE' => 'gzip', 'DL_FUNCS' => {  }, '
+FUNCLIST' =
> [], 'IMPORTS' => {  }, 'DL_VARS' => []);"
        dlltool --def gzip.def --output-exp dll.exp
        g++ -o blib\arch\auto\PerlIO\gzip\gzip.dll -Wl,--base-file -Wl
+,dll.base -mdll -L"C:\Perl5.10\lib\CORE" gzip.o -Wl,--image-base,0x49
+1e0000  C:\
Perl5.10\lib\CORE\perl510.lib -lkernel32 -luser32 -lgdi32 -lwinspool -
+lcomdlg32 -ladvapi32 -lshell32 -lole32 -loleaut32 -lnetapi32 -luuid -
+lws2_32 -lm
pr -lwinmm -lversion -lodbc32 -lodbccp32 -lmsvcrt dll.exp
gzip.o:gzip.c:(.text+0x4fe): undefined reference to `inflateInit2_'
gzip.o:gzip.c:(.text+0x5b7): undefined reference to `crc32'
gzip.o:gzip.c:(.text+0xac0): undefined reference to `deflateInit2_'
gzip.o:gzip.c:(.text+0xafe): undefined reference to `crc32'
gzip.o:gzip.c:(.text+0xf3d): undefined reference to `crc32'
gzip.o:gzip.c:(.text+0xfed): undefined reference to `inflateEnd'
gzip.o:gzip.c:(.text+0x101d): undefined reference to `deflateEnd'
gzip.o:gzip.c:(.text+0x12c5): undefined reference to `inflate'
gzip.o:gzip.c:(.text+0x13d2): undefined reference to `crc32'
gzip.o:gzip.c:(.text+0x14ba): undefined reference to `deflate'
gzip.o:gzip.c:(.text+0x1618): undefined reference to `crc32'
collect2: ld returned 1 exit status
NMAKE : fatal error U1077: 'C:\Perl5.10\site\bin\g++.EXE' : return cod
+e '0x1'
Stop.
[download]

Update: In the example above I used nmake. However, afterwards, I reconfigured my system to use dmake instead and got the same result.

Update/Solution: I found that using the MSYS zlib-dev distribution finally worked. http://sourceforge.net/projects/mingw/files/MSYS/zlib/zlib-1.2.3-2/zlib-1.2.3-2-msys-1.0.13-dev.tar.lzma/download. This delivers a set of two directories, include and lib, which contain resp. headers and precompiled library files. The other trick that I had to do to make this work was that the lib files had to be placed in the <Perl5.10>\lib\CORE directory.