Malware + Firefox = Head Explosion

My computer knowledge barely extends past the use of Open Office so you'll have to excuse me if this is a stupid question.

I'm using an old laptop (my one died but that's a whole different story) I've noticed over the past few weeks since I got it that every time I google something in firefox (i'm running 3.5.5) the search result redirects me into some random search engine or webpage. I'm pretty sure it's some sort of malware/spyware but I have no idea how to get rid of it.

I've tried using AVG to scan the program files of Firefox but it's not picking anything up. I've also tried uninstalling and reinstalling firefox but that doesn't work either. Can anyone recommend something for me to do?

Any help is much appreciated.