Problem: The Google Search add-on is missing from the Internet Explorer Gallery.


Solution: Go to http://www.iegallery.com/en/addons/detail.aspx?id=813 and add Google as usual.


Source: http://answers.microsoft.com/en-us/ie/forum/ie8-windows_vista/cant-install-google-search-provider/c2d57255-39dc-4203-8461-98266952ffa0