I tried some search on Japanese Wikipedia, which was of course off, and I was redirected to the Google. But the problem was - the request URL didn't contain encoding information.

&ie=UTF-8&oe=UTF-8 should be added to the request URL.