Researchers at AT&T Research Labs have published a paper (PDF) about counting hosts behind NAT devices.

The short version is that they take advantage of the poor use of monotonically increasing packet ID numbers in IP packets sent by different hosts to track the number of hosts that are sending requests through a particular NAT device. Since most OS's (except FreeBSD and OpenBSD, but I'm not sure about Darwin - somebody post a comment if they are) use a monotonically increasing number for this packet parameter, you can figure out how many unique hosts there are behind a NAT device if you have a way to monitor all traffic. Basically, you watch the ID's and look at the patterns to see how many sequences there are.

Fortunately for users of FreeBSD and OpenBSD, the use of pseudo-random numbers for the ID makes it nearly impossible to figure out.