複数のカテゴリーを選択しての検索

商品をカテゴリーで分けているのですが、（料金、メーカー、タイプ等）
複数のカテゴリーをラジオボタン等で選択して検索ボタンを押して検索したいと思っています。

検索は AND 検索ですか? OR 検索ですか?

カテゴリーをタグに変換してしまえば、複数タグの AND 検索または OR 検索は比較的簡単にできます。

http://blog.example.com/?tag=赤色+Tシャツ (AND の例)
http://blog.example.com/?tag=青色,緑色 (OR の例)

ただ、こういう URL をチェックボックス等のフォーム部品でいきなり作るのは難しいので、一度 PHP スクリプトでフォームを受けて URL を合成してリダイレクトするとか、JavaScript でフォームを操作させるとかの手が必要になります。

もう少し具体的に、どういうカテゴリーが存在して、それらの組み合わせパターンがどれだけあるか提示してもらえないでしょうか。それらの数によっては、あらかじめ全部の組み合わせを作っておいて、そこから選ぶだけ、とすれば比較的簡単に作れます。
そうでない場合は、カスタムの PHP スクリプトが必要なので、ちょっと大変です。商用目的なのであれば、PHP や WordPress に詳しい業者に依頼した方がよいかもしれません。