If cookies are cleared, there is no way if you hadn't gotten them to self identify first.
You want to get users to self identify with an email address of some kind as quickly as possible. Then you want to utilize the
Tracker.Current.Session.Identify (string identifier) method in order to convert the anonymous user to a Known Contact.
The Identify method merges interactions from the anonymous contact to the known contact.
Once a user is Identified through that method, all interactions going forward are logged to the known contact.
If this user walks away without logging out specifically (nor doing a
Tracker.Current.Session.EndVisit()), if the session timeout doesn't occur, then the next person browsing on that computer will be of that contact.
Care should be taken to adequately Identify as well as log out contact visits.
You have to find some kind of information that they would be willing to give you, that can be unique enough. So then in that example, you could, generate a user code dynamically and
Identify() with that generated code that is unique enough.
The next time they come back, have some process where they provide that code you gave them, and you can pick up the contact record by Identify using that code.
The moment that they provide an email address, identify with the user code first, then modify the contact record (and change the identifier to the email address.
If you need examples on how to edit the contact record, I've a few on my SitecoreHacker.com blog.