1. Берете характеристики товаров, которые могу участвовать в фильтре, получаете для каждой характеристики все варианты значений для текущей выборки товаров.
2. Выводите в форму фильтра, значения сгруппированные по характеристикам с инпутом-checkbox.
3. Пользователь ставит галки, отправляет форму.
4. Формируете критерий для выборки из базы на основе запроса.
5. Переходим к пункту 1.
Для ускорения: индексы, кэш, sphinx