I use firefox (mainly on linux but also on windows), and I have it set up to delete cookies and browsing history every time I exit. Despite this, every time I come to tex.stackexchange.com, I am recognized a few seconds after I connect. How is this done without cookies?
Traditional browser cookies are by no means the only way to store tracking information. For example there are also cookies stored using Adobe Flash (use this site to configure flash storage).
EDIT: My original guess turns out to be wrong. They seem to use HTML5 local storage, as described in a blog post. One way to somewhat reliably remove tracking information is the BetterPrivacy Firefox addon (I haven't tested that extensively, but it seems to work for stackexchange).