Объясните на пальцах, как работает сжатие WinRAR?

Популярно.
RAR, ZIP, ARJ и прочие - это лишь различные форматы архива, контейнеры. Как правило, архиваторы последовательно используют несколько алгоритмов сжатия, далее сжатые данные размещается в контейнере вместе с информацией об использованных кодеках. Все алгоритмы сжатия без потерь делятся на 2 большие группы - потоковые алгоритмы и блочные. Потоковые алгоритмы - могут работать в потоке - то есть, грубо говоря, на вход алгоритма поступают данные последовательно, хоть по одномы байту, на выходе тоже последовательно появляются сжатые данные. Это алгоритмы Хаффмана, примитивное кодирование длинных серий (пару лет назад курсовик знакомой делал - разработка архиватора на базе этой байды и наиболее совершенные из них - большое семейство словарных алгоритмов Лемпеля-Зива (LZ, LZW, deflating и др.).
Блочные алгоритмы отличаются тем, что для сжатия информации они должны изначально знать весь кусок сжимаемых данных. На практике, если входной файл большой, он разбивается на блоки, каждый из которых сжимается отдельно. Поэтому в потоке данные алгоритмы могут работать только так: накопить из входного потока блок данных, потом сжать его разом и выдать на выход. Эти алгоритмы более эффективны, чем поточные, но требуют больше ресурсов (и вообще довольно сложны для понимания, как там это все работает Примеры - алгоритм Барроуза-Уилера (перестановок), семейство PPM алгоритмов (самые сильносжимающие на сегодня, но и самые медленные). Их, наряду с поточными и используют современные архиваторы, напр. RAR, 7zip и даже совсем не новый ha (если кто помнит такой еще под DOS, жал тексты как черт, но очень медленно).
Помню точно, что RAR использует PPM, какой-то LZ-подобный алогритм и кодирование Хаффмана - а в каком порядке они применяются к сжимаемому блоку - уже не помню.

Ну, блочные появились из-за того, ИМХО, что на поточных словарей не напасёшься. А полностью опустошив словарь (по переполнению сразу или постепенно — не важно), то преимущества потокового сжатия теряются. Хотя всякие мпеги работают с потоками и ограниченными словарями.

Благодатная тема. Народ кинулся делиться знаниями. Изложу свое видение.

Информация может сжиматься без потерь данных и далее полностью восстанавливаться с точностью до байта различными способами

1) кодирование наиболее часто встречающихся букв (цифр и т.д.) более короткими кодами, а редко встречающихся - более длинными. Например буквы Е, А - встречаются в текстах очень часто их можно записать не 8 битами, как в исходном тексте, а тремя или даже двумя, зато другие буквы нам придется кодировать даже не 8, а гораздо большим количеством битов. Какой-нибудь букве Х может придется отвалить битов 11-12. Такое кодирование известно как кодирование Хаффмана. Есть и другие случаи реализации данного принципа. Например довольно известная азбука Морзе В ней самой распространенной букве Е присвоен самый короткий код - точка (.), буква А кодируется уже точкой-тире (.-), а буква С - тремя точками (...)

2) кодирование последовательности одинаковых символов, оно же RLE кодирование. К примеру имеются байты ААААААААА. На них можно не тратить целых девять байтов, а описать все как "9 букв А". Слову "букв" присваивается некий условный и не слишком длинный код. Если повторяющихся данных много, то этот метод дает хорошие результаты.
Повторяющиеся данные характерны например для рисованных вручную картинок, где имеется постоянный фон в сотни повторяющихся точек и мазки в которых повторяющихся точек тоже достаточно много.

3) выделение многократно встречающихся сочетаний символов и составление словаря таких сочетаний. Далее значения, вошедшие в словарь, в самом исходном тексте заменяются на короткие условные коды. А к сжатому файлику добавляется этот словарь, чтобы при декодировании можно было подставить всё обратно. Это LZ-кодирование.

Архиваторы используют обычно несколько методов сжатия.

Есть ещё функциональное сжатие. Но это больше для специфических данных. Типа ряда Фурье — коэффициенты и шаг сетки, а не множество точек.