Generally we do not feel OAuth 2.0 you should store tokens
Now you have to worry about securing your database and the data in it - these tokens give access to some fairly privileged information about your users. Of course, simply storing the token in sessionStorage might put it on disk too, depending on your session configuration. Its a good idea to keep it encrypted while you're not using it.
Your proposed scenario about the user clearing cookies and coming back is also an issue. You could take the access token from the database and stick it back into their cookies, but before you do that, you have to make sure they are who they say they are - and now you have to do another layer of passwords just to give them access to the token they already gave you.
You're probably better off simply re-doing the authorization flow when they come back and click the login button again. Its not that expensive. But if that truly is a showstopper for you, then storing the token is an option. You'll just have to be really careful about working through all the associated issues.