I never quite understood why using localhost as the host name did not work with Magento, for example when developing on your laptop Using 127.0.0.1 works, but localhost does not. For a while I thought it was some weird Magento restriction I did not understand, but the penny finally dropped when someone explained it (again) to me recently.
https://stackoverflow.com/questions/1134290/cookies-on-localhost-with-explicit-domain#16652347 has a good description. It is not Magento, it’s that web browsers behave differently when used with a domain name with less than 2 dots in it, such as localhost. The cookies are not saved.
So the easiest solution is either to use 127.0.0.1 or add a domain name to your local hosts file (/etc/hosts under Linux or C:\WINDOWS\System32\drivers\etc\hosts on Windows) with something like the following in it.
Using http://www.mydevbox.com as the domain name will then result in cookies behaving correctly. Mystery solved!
(I will leave deeper explanations to brighter minds than mine…)