In the gzip case, the reason is that the compressed stream format is inherently sequential: you need to decompress everything before a byte before you can decompress the next byte. So parallizing is not really possible, without changing the format.

Newer compression formats have multiple streams that can be decompressed in parallel, or have blocks that are compressed independently without dependencies (bzip2 can be decompressed in parallel due to independent blocks).