How does Google Instant change the referer sent by the browser?

Most of the time, a Google search result actually sends you to a Google redirect page rather than directly to the target page. They use JavaScript to switch the target of the link onmousedown as you click on it.

You can see this effect by click-and-holding on the search result link and watching your status bar.

This isn't specific to Google Instant, they've been doing it for quite a long time on their standard results pages.