What my framework (Django) does, and I assume this is simialr to other frameworks, is this: it creates a user object (see note) in the database, then keeps the user object id in a cookie on the user's computer. This is, by Django's default, kept on the user's computer for 2 weeks before being removed (and it can be made to never be removed).
Using this, you can store any information you want about a user in their user object in the database, and always have that information available to you via the cookie.
Note: by default, Django creates an "AnonymousUser" object for each visitor, not a real user object, and it is up to the site to create an actual user object. To implement that "PhantomProfile" that Fred Wilson is talking about, I usually make Django create a new user object with a temporary username, and use this instead of AnonymousUser objects. In this way, when they do decide to "register", I just keep the same user object and give it a new username.
I'm not sure I follow you.
If a user isn't one of the "fringe" group which doesn't allow cookies, then you can store a cookie identifying the user to you, create a profile for them as if they are a regular user, and track anything you want. You can treat them like regular users, or treat them in a special way, but either way you can store any information you want.