Você está quase lá. Tente isto:
zgrep -R -H "foo" *.gz
EDITAR: Hmmmm .... intrigante!
De acordo com o meu zgrep, -R (recursivo) não é uma opção. Simplesmente não é suportado. Eu tenho um cheque para ver o que a página de manual do seu zgrep diz.
Uma alternativa, que depende de apenas um nível de subdiretórios, é fazer isso:
zcat */*.gz | grep <needle>
Mas sugiro que seu comando de busca seja provavelmente melhor!