Upgrade the links with jQuery. Here's a simplified version of what I use:

    $("a").bind("mousedown", function(e) { 
        $(this).data("href", $(this).attr("href"));
        $(this).attr("href","http://example.com/redirect?url=" + $(this).attr("href"));
    });
    $("a").bind("mouseup",function(e) {
        var el = $(this);
        setTimeout(function() {
            el.attr("href", el.data("href"));
        },10);
    });

This works by switching the url when a user clicks a link to your redirect url, then switching it back a fraction of a second after they mouse up. This means that your redirect works even if the user right clicks and opens in a new window / tab and when a user hovers over a link, they still see the normal URL in the status bar.

On the /redirect url just log any data you need and send a 301 or 302 redirect. The destination site will see your original page as a referrer, not your redirect url.