Entre na pagina: http://www.microsoft.com/windows/ie/searchguide/pt-br/default.mspx Na pesquisa, clique em “Adicionar mecanismos de busca ao Internet Explorer”, e na próxima página é so escolher o provedor desejado, clique em “Substituir”.

Pronto, o provedor de pesquisa foi trocado.

11/01/12
Pessoal a Microsoft tirou do ar a pagina citada acima então consegui uma nova solução que seria baixar o arquivo:
google_br.reg.zip
Descompacte e execute o arquivo .reg que o Google em português já será o seu provedor de pesquisa padrão.