zgrep é seu amigo!
Zgrep invokes grep on compressed or gzipped files. All options speci‐ fied are passed directly to grep. If no file is specified, then the standard input is decompressed if necessary and fed to grep. Otherwise the given files are uncompressed if necessary and fed to grep.
Acabei de notar que algumas versões do zgrep não têm uma opção -r. Nesse caso, você pode usar seu padrão de localização para capturar todos os arquivos e usar o zgrep em vez do grep, como:
find . -type f -exec zgrep 'my search string' "{}" \;