If you know what you're looking for in the user's browser history there is a pretty simple way to check if the user have visited a certain site recently or not. Basically you can create an invisible iframe with the link(s) you want to check and then use java script to query the appearance of the link. CSS tell you if the link is visited or not. A more detailed description on how this works can be found here. The way this exploit is used there is actually quite nice I think, since it enhances the user experience. And I have no problem with ads customized to match my browser history. I usually don't see them at all because of the ad blocker but if I could get ads that I'm actually interested in this would also enhance my user experience. So far no harm done. I guess the problem with this exploit is that phising sites like those impersonating a bank or paypal could now customize their phising attack to match the bank (or other service) the user actually have visited recently.
If you use Firefox (which have tried to fix this since 2002) there is a plugin to fix this.