10.08.03追記：この記事を見てくれた方へ
ごめんなさい、以下の内容は検索エンジン側が &charset=UTF-8 でパラメータを受け付けるときのみに有効な方法でした。つまり間違いです。

サイトの検索で外部検索エンジンを使うときなど、サイトはUTF-8なのに用意された検索エンジンはShift_JIS、、のようにサイトと検索エンジン側の文字コードが違う、というのはよくある話で、そうすると文字化けを起こします。

hiddenパラメータで文字コードを送る

そういうときはhiddenパラメータでサイト側の文字コードを埋め込んでおくといいです。

以下のようにform要素に入れておきます。

accept-charset属性

formのaccept-charsetという属性で検索エンジン側の文字コードを指定することでも回避できるようですが、IEが未対応なようで、実用的ではないです。