On occasion I change my MAC address from time to time at a public Wifi service. However lately something has changed. The captive portal (Wifi) remembers me even if I change my MAC address on my Macintosh. How is that possible? Is it leaving a cookie on my computer somehow? If so, how to remove it?
The obvious answer is that it's using a cookie, but I assume you've cleared those. Try clearing them pre-connect, and see what cookies are added post-login.
You will learn nothing useful (for solving your problem) by running tcpdump or wireshark. If you run it anyway, do a capture of 2-3 login sequences, and build filters later. I don't use wireshark, so can't help with those, but a tcpdump pcap filter may look like this (for capturing a HTTP captive portal session):
sudo tcpdump -ni en1 -s 4096 host 192.168.1.2 and port 80,
where en1 is your wireless interface and 192.168.1.2 is the IP of the captive portal.