This might not be possible if all cookies are cleared and you haven't gotten them to self identify first.
Ideally, 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 mergers interaction 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 visitis.
You have to find some kind of information that they would be willing to give you, that is unique. So 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.)
I should mention, this is a moot point if they haven't cleared cookies. It'll keep the same ID, but the cookies being cleared really requires that some kind of information is provided by them in order to make the connection.