The 'xzgrep' script (and related xzdiff, xzless, xzmore scripts) are part of the standard xz package, though they are an optional feature so YMMV between distros.

    ~ $ xx /usr/portage/distfiles/xz-5.0.8.tar.gz
    ~ $ cd xz-5.0.8/
    ~/xz-5.0.8 $ ./configure --help | grep -A1 scripts
      --disable-scripts       do not install the scripts xzdiff, xzgrep, xzless,
                              xzmore, and their symlinks

zgrep simply decompresses all the data and feeds it into regular grep. If the data is indexed in some way, it is possible to do better by not having to look at all the data exhaustively.