Depende, existem vários algoritmos diferentes, cada um com seus prós e contras. Dadas as suas características, um pode ser melhor para determinados tipos de dados (texto com muita repetição, ou imagem, etc), outro pode ser bom para uso geral mas é mais lento que os outros, etc.

Enfim, no link acima tem um resumo básico de vários algoritmos. Se quiser entrar em detalhes, pode fazer buscas sobre "how [algorithm] works" - não vale a pena detalhar um a um, pois todos costumam ser complexos e geralmente as buscas específicas te darão todos os detalhes.

Só pra citar um exemplo, uma forma comum para compactar texto é criar uma estrutura que contém as ocorrências de determinadas partes. Simplificando bastante (pois os algoritmos reais são mais complexos que isso), vamos supor que eu tenho um arquivo texto que possui a palavra "algoritmo" 5 vezes, nas posições 1, 25, 42, 100 e 200. Ou seja, só essa palavra ocupa 9 bytes, vezes 5 ocorrências, dá um total de 45 bytes (supondo que o arquivo foi salvo com um encoding que codifica caracteres ASCII com apenas 1 byte, claro).

Um algoritmo bem rudimentar para compactar seria criar uma estrutura que contém a palavra e uma lista das posições em que ela aparece. Ou seja, eu preciso dos 9 bytes da palavra, e mais 5 bytes referentes aos números (total: 14 bytes). Faço isso para todas as palavras. Mais ainda, posso fazer para sequências de caracteres (podendo ter várias palavras inclusive) que se repetem com mais frequência, pois daí eu maximizo a economia de bytes. No final o arquivo compactado só tem essa estrutura (o mapeamento de sequências de caracteres e suas respectivas posições). Na hora de montar o arquivo original, basta ir lendo as posições e escrevendo a sequência novamente.

Como eu disse, essa é uma versão bem simplificada, pois os algoritmos reais são mais complexos. Sem contar que esse exemplo que citei funciona melhor para texto, mas só se tiver muitas repetições. Para imagens, músicas e vídeos, são usados outros algoritmos, dada a natureza bem diferente dos dados (e como já dito, compensa mais pesquisar um algoritmo de cada vez).