I'm posting on HN to get the low down if anyone who has ACTUALLY first hand know how on how this is accomplished.
If you are on their network then they can see your MAC address. That's how Ethernet works.
See http://en.wikipedia.org/wiki/MAC_address#Spying for an example of how Apple has changed iOS so it uses a random MAC address. See also http://security.stackexchange.com/questions/6868/randomizing... .
Note: the above is a 10,000 foot observation of what happens.
More in-depth: https://en.wikipedia.org/wiki/MAC_address
What they will likely do is take your IP and look to which MAC their DHCP-Server has assigned that IP to. There are other possibilities though, but they are more complicated (using ARP-cache or requests, doing a raw packet dump at the webserver).
If you want learn more, I think you could read a bit about the different layers first, and then read about how ethernet, IP/ARP and DHCP work. There are likely no "headers" (I assume you mean HTTP-headers) they inspect.
What you're asking is, in essence, "how does ethernet work?" That cannot be explained in a few paragraphs. You can start with Richard Stevens' "TCP/IP Illustrated, Vol. 1", as one of many available descriptions. You can use Wireshark to track all of the details.
At this point you should stop asking questions here. There's likely no simple answer, and this is a great chance to experiment and figure it out for yourself.
(Even if someone knows the exact details of how Starbucks does it, you are unlikely to understand the explanation without understanding some of the fundamentals.)