When you say that you Google something, are you interchanging "search" and "Google"? Go to google.com instead of typing in the address bar or search bar and check if this still happens.

If you are searching from the search bar, go to http://mycroft.mozdev.org/ and reinstall the Google search engine. I suspect that a program may have installed another search engine and set it as the default.

These articles may help: http://www.firefoxfacts.com/2008/01/13/change-default-search-in-firefox/

Do a malware check with a few malware scan programs.
You need to use all programs because each detects different malware.
Make sure that you update each program to get the latest version of the database before doing a scan.

• http://www.malwarebytes.org/mbam.php - Malwarebytes' Anti-Malware
• http://www.superantispyware.com/ - SuperAntispyware
• http://www.safer-networking.org/en/index.html - Spybot Search & Destroy
• http://www.lavasoft.com/products/ad_aware_free.php - Ad-Aware Free
• http://www.microsoft.com/windows/products/winfamily/defender/default.mspx - Windows Defender: Home Page

See also "Spyware on Windows": http://kb.mozillazine.org/Popups_not_blocked and What to do when searches take you to the wrong search website