I'm assuming you're talking about the typical "Service Provider," "Consumer" and "User" setup?
If so, the session and cookies are good enough for saving tokens, but the problem is that it's your Consumers (your clients, as I understand) that need to be saving them and not you. Is there a session/cookie available in the scope of the calls to your API?
In either case, if the tokens are stored in the session or cookies, they will be "temporary" keys and the User will have to re-authenticate when they expire. But there is nothing wrong with that as far as the oAuth spec is concerned - as long as the Users don't mind re-authenticating.
Also bear in mind that the tokens are tied to a given service and user, and not to any IP address or device UUID, for example. They could not be used with different API and secret keys, as they are tied to the application they were issued for.
This way the user can de-authorize on a by-application basis, and every app can have a different set of permissions (e.g. read-only access). So your answer is you don't need to encrypt them, and you need them in plaintext anyway (if you're the User).