urlencode를 해 주셔야 합니다.

이런식으로요.

http://search.naver.com/search.naver?query=urlencode($Search)

urlencode() 함수는 한글과 특수문자를 16진코드로 변환하고

중간의 빈칸은 + 로 변환합니다

물론 영문은 엔코딩이 필요없죠.

url 을 엔코딩해서 넘겨주어야하는이유는..
브라우져가 한글이 포함된 url 을 잘 인식하지 못함인데요.

naver.com 에서 "네이버" 로 검색을 해보면 주소가

http://search.naver.com/search.naver?query=urlencode("네이버")

와 같이 "네이버"라는 한글문자를 엔코딩하여 url 로 넘겨줍니다.

물론 POST 보다 GET 이 빠르니 GET 전송하고 있고요
이 주소의 끝을 직접수정하여

http://search.naver.com/search.naver?query=네이버

라고 해줘도 브라우져에서는 잘 보입니다.

하지만 브라우져의 고급옵션에서 "URL 을 UTF-8 로 보냄" 으로 설정되어 있는

경우는 한글URL 을 잘 인식하지 못하기때문에
반드시 엔코딩이 필요한것입니다

물론 이렇게 인코딩해서 보내주면
받는페이지에서는 특별한 조작없이
원래의 값을 그대로 얻을 수 있습니다

출처 : Tong - 드렁크수달스님의 ■ PHP ■통