And when someone clicks on a targeted ad, is their identity still private? Or does the company get a handy referrer that allows them to correlate that user's Facebook profile (and hence real name) with the specific criteria they paid to filter by?

It seems to me they have quite a lot to do with each other, in that Facebook has an enormous amount of valuable personal information about people (which in many cases was extrapolated without the target's consent, as opposed to explicitly given), and is entirely reckless about where this data ends up, as long as it isn't actually "public" as such.