Hay dos clases de compresores, lossless (sin pérdida) y lossy (con pérdida).

La primera clase se usa cuando la información debe preservarse en su totalidad, un ejecutable por ejemplo.

La segunda clase suele usarse en imagenes, video y sonido, aqui la perdida de la información no es demasiado apreciable.

Los más faciles de codificar son los primeros, pero su nivel  de compresion suele ser inferior que la segunda, los algoritmos mas conocidos son Huffman, LZ77, LZ78. Busca estos topicos en google y vas a tener paginas que los describan en detalle.

Para la segunda se suele usar la transformada de cosenos, y mas recientemente la transformada wavelet.

Se pueden programar en cualquier lenguaje decente, la mayoria tienen implementaciones en C. En algunos lenguajes hacer las implementaciones suele ser mas dificil, p.ej. en VB que no permite manipular de manera sencilla bits dentro de un byte.