Currently with Internet Explorer 9 if you attempt to add a new search provider in Australia by selecting Manage add-ons, Search Providers, and then click on Find more search providers … you’ll be presented with a very meager listing, which doesn’t include google search. The solution is quite simple.
By default you are presented with your regional location search providers. The url is something like this: http://www.iegallery.com/au/addons/?feature=searchproviders. In this case the region is au (Australia). If you change the region to en (English), as in this: http://www.iegallery.com/en/addons/?feature=searchproviders you’ll be presented with a plethora of search providers including Google. The last step is to install the Google search provider and set as default if you desire.