Firebug and Chrome's dev tools both reliably stated that the cookie header was indeed being set. I just didn't know why Firefox was accepting the cookies and holding the sessions, but Chrome was dropping the sessions.
Oddly, it was only happening on my virtualbox dev environment, and not on any production machines.
After much time, I noticed that the expiration date for the cookie was in the past. I hadn't noticed it before because it looked right (it correctly passed my mental regex for "looks like a good date").
It turned out the problem was being caused by my machine going to sleep, pausing everything (including the clock timer in the VirtualBox instance, which I leave on for weeks or months), causing the clock on the virtual server to get behind by several days.
Then, when setting the cookie expiry date in max-age format, rather than absolute time, Mochiweb would send the Max-age expiration, which then gets handled by the browser relative to the receiving time. But Yaws would first take server time, add the seconds, and send that as the absolute expiration, effectively sending an past date to the browser as the expiration.
Firefox, apparently, saw the cookie expiration date, and just said something like "Hey, we'll hold this until the user closes the tab or something", while chrome saw the expired cookie, and immediately expired it, appropriately.
That's one of the weirdest non-bug bugs I've encountered.
Note: when I say "Yaws" and "Mochiweb", I mean "Nitrogen's SimpleBridge connector for Yaws and Mochiweb".