Tomcatのserver.xmlのConnector要素に以下の属性を設定する。
URIEncoding --- URIをデコードするときの文字エンコーディング。デフォルトはISO-8859-1。
useBodyEncodingForURI --- URIパラメータのデコードにサブミットしたフォームのページの文字エンコーディングを使用するかどうか。デフォルトはfalse。
(Apache Tomcat Configuration Reference - The HTTP Connector)
例:

<Connector port="8080" protocol="HTTP/1.1" 
       connectionTimeout="20000" 
       redirectPort="8443"
       URIEncoding="UTF-8" useBodyEncodingForURI="true" />

Tomcat5/6のGETリクエストで文字化け - @"かたち開発の開発日記"
Encoding problem for czech characters in HttpRequest parameters - Spring Community Forums