Amazingly, as low as 50 bytes though 300 is more typical using developer Scott Vokes HeatShrink a C library devised specifically for embedded systems where the amount of ram is low. The CPU doesn't have to be fast either.
Scott posted a blog entry where he describes HeatShrink and compares it to gzip in compression ratio and memory used. For some file types, compressing using 48b of ram is clearly not ideal (-ve compression- it gets bigger!) but for others it's not bad.
- Permanent link added to Linux C Code Library