OP:"I have Firefox set not to remember my history."

This will not have the effect you seek. Websites cannot access your browser history - or only in very limited ways like colouring visited links. Without history you lose useful features, like the ability to find a site again by keying in a bit of its name.

As already mentioned, it's mainly cookies - though there are other ways. Stopping google from tracking you is next to impossible.

The 'Do not track' flag was a nice idea but almost totally ignored by advertisers.