JPEG compression is a good overview of how all lossless compression is done. It is indeed complicated. It compresses the image in the frequency domain using a kind of Fourier transform, then gives the most bits to the frequencies that have the most effect on the image signal. Those bits are then encoded using huffman and RLE. Additionally, the encoder will give more bits to chrominance than lumincance, and various other details like that. For movies, macroblocks are considered, which are smaller squares of images in each frame of the movie. Motion is detected for these images, so only new macroblocks are generated for the ones that change.
Granted actual implementation is much, much more detailed and complicated than this.
