When does Magento use sessions and when cookies?

No, that means that sessions are persisted with a cookie, which contains the ID of the session. The only alternative in PHP is a URL parameter like ?SID=d41d8cd98f00b204e9800998ecf8427e where d41d8cd98f00b204e9800998ecf8427e is the session ID.

In Short, session data are stored on the server but since HTTP is stateless, a cookie or parameter with the session id is necessary to identify the right session.

Magento sets two session cookies, adminhtml for the backend and frontend for the frontend. Session models like 'checkout/session' store their data in a "namespace", i.e. $_SESSION['checkout'].

Session-unrelated cookies that Magento sets, are for example the store cookie that remembers, which store view you currently browse.