The question on Information Security linked in the comment above has a lot of relevant information. That being said, a few additional concerns raised in this question should be addressed:
Safety
Knowing nothing about the server implementation, both methods can be as secure. Session-based authentication mostly relies on the guessability of the session identifier (which, as described in the Information Security answer, it in itself a very simple token). If the session identifier is a monotonously incrementing numeric id, then it is not very secure, OTOH it could be an opaque cryptographically strong unique ID with a huge keyspace, making it very safe. You are probably going to use the session implementation offered by your server framework of choice, so you need to check that. After that, using session authentication, your server implementation needs to verify that the server stored session contains the relevant authorization (i.e. user account data, role, etc) - as a lot of server session frameworks will be default auto-generate empty sessions as needed, the fact that a session exists must not be relied upon as proof enough for a valid authentication and authorization.
For example, PHP's internal session ID generation uses a completely random 288 bits number (default setting) so it is considered safe, OTOH - by default it generates sessions automatically so the previous comment must be adhered to (or to disable automatic session creation and make sure the server only creates session as needed).
Also, if the session ID is passed using an HTTP URL query string, as was the default in days of old, then the session can be stolen quite easily and that makes the whole process insecure.
Token safety is mostly based around secure token generation: if the server generates tokens in a secure manner - i.e. non-guessable and verifiable - as demonstrated in the Information Security answer. A naive implementation (that I saw one time) might be to MD5 hash a known token, such as a user name, and that makes it very unsafe, even when salted. When using cryptographic tokens, safety is closely related to the strength of encryption which is determined by the algorithm used, length of the key, and - most importantly - how well the server key is secured: if the server key is hard-coded into the server implementation and that code is then open-sourced...
Storage
Whether the server needs to store anything generally depends on the implementation of the tokens.
A lot of implementations use the concept of an "API key" as "token authentication" and so often tokens are just some cryptographically secure ID to a database that records which "API keys" have been generated. This requires storage but has the advantage of a simpler implementation and - more importantly - the ability to revoke tokens.
The other approach is to have the token carry its own authenticity - this allows the server to essentially offload the storage of tokens to the client and use the client as the database - very much like how HTTP Cookies allow servers to offload some storage requirements to the client (often used for client's specific settings, like whether the user wants a light interface or a dark interface).
The two patterns used for this are demonstrated well in the Information Security answer: signing and encrypting.
Signing: The token is some simple encoding (like JSON or CSV) of the authenticator credentials (such as the username) and possibly the token's expiry time (if you want to have tokens expire - generally a good idea, if you can't revoke tokens), and then the server signs the generated text using a server secret and adds that to the token. When the client submits the token, the server can extract the clear text from the token, re-sign it and compare the new signature to the signature part in the submitted token - if they are identical, then the token is valid. After validation, you probably want to check the validated expiry date against the current time. The main disadvantage here is that care should be taken that the clear-text authentication details are strongly insufficient for an attacker to re-authenticate - otherwise, it harms the safety requirement. i.e. don't send the password as part of the token, or any other internal detail.
Encrypting: the token is generated by again encoding all the relevant authentication details and then encrypting the clear-text with a server secret and only submitting the encrypted result. If the encryption scheme can be trusted, the authentication details can include internal data - but care should be taken as having a large crypt-text available offline to an attacker is a larger attack surface than a small signature and weak encryption algorithms will be less resilient in this usage than in just signing.
In both methods, safety is closely related to the strength of the encryption/signing algorithm - a weak algorithm will allow an attacker to reverse engineer the server secret and generate new valid tokens without authentication.
A personal note
In my opinion, cryptographic token-based authentication tends to be less safe than session-based, as it relies on the (often single) developer doing everything right from design to implementation to deployment, while session-based authentication can leverage existing implementations to do most of the heavy lifting, where it is very easy to find high-quality, secure and massively used and tested session storage implementations. I would need a very compelling reason as to why session storage is unwanted before recommending using cryptographic tokens.
Always remember the no.1 rule of cryptographic security: never design your own single-use cryptographic measures.
