GNU Zip (or gzip for short) is a stream compression program (like the UNIX compress program), and not an archiver (like the DOS pkzip program) that uses an unpatented (and unpatentable) algorithm for its compression. The program bzip2 can compress even more, but takes more memory to do so. The zlib library uses the same algorithms, and can be used to process or produce gzipped files (IIRC, though there might be a header too.)
This governed by two RFC's
See also http://en.wikipedia.org/wiki/Gzip