Javascript injection only when referred by search engine.

My website has some weird malware installed in it. When I click on a link from a search engine (google, bing, or even yahoo) my pages get a string of javascript inserted into them. The page can be a simple "Hello World" and it will still inject a line of javascript into the page. Here is a screen shot of the Avast warning I get.

It's weird because I don't know where this code is coming from. It magically injects itself into all the pages.

Is this a rootkit ? How do I remove it ? I know very little about security, are there firms that don't cost big bucks ? Is there Malware scanning utilities I can use to so scan my server ? It's running debian.

Thanks a lot

It could be that your webserver itself(i.e. apache) is compromised. I've seen it happen by somehow replacing an innocuous library that apache uses with a tainted one. I had to compare md5sums for all installed programs on the system to track it down, fortunately gentoo gives means to do that..

It's also possible it's a problem with your web browser, though. firefox uses javascript to do nearly everything. Does avast still go bananas if you use any other browser?