Agrego más info conceptual y corrijo algunas cosas. Es largo porque quería explicar el panorama general para enmarcar la respuesta:
1) Una sesión es un concepto bastante abstracto, presente en varios programas (no sólamente web). Vamos a definirlo así: una sesión es un conjunto de interacciones entre un usuario y una aplicación, enmarcado por un evento de "inicio" y uno de "fin". Por ejemplo, me logueo con mi usuario en mi computadora, trabajo durante 3 horas, me deslogueo. No necesariamente los eventos de inicio y fin tienen que ver con la autenticación del usuario. Por ejemplo, varias aplicaciones permiten trabajar en modo "invitado" o "guest", incluyendo algunos sistemas operativos. Por este motivo, en general a los eventos se los denomina "Inicio de sesión" y "Fin de sesión".
2) Una sesión en general acarrea estado entre cada una de las interacciones individuales que la comprenden. Por ejemplo, en las interacciones "me logueo en gmail, mando un mail, me deslogueo", cuando mando el mail, la aplicación recuerda quién soy de cuando me loguié. Esto significa que entre interacción e interacción hay algún tipo de mecanismo que le permite a la aplicación guardar estado (quién soy) en la primer interacción, para después acceder a ese estado en las subsiguientes interacciones.
3) Ahora si, nos metemos en la web. HTTP pelado es un protocolo que no permite almacenar estado entre request y request, lo que significa que entre cada interacción (request en http) no hay forma de mantener estado para los subsiguientes requests de esa sesión. Para poder saltear esta dificultad, HTTP provee un mecanismo en el que en la respuesta de un request se le puede indicar al cliente algo como "a partir de ahora, cada vez que me hagas un request enviame además del request el siguiente dato". Esto permite, por ejemplo, que en el response de la acción de loguearte el server le avise al client "a partir de ahora, adjunta a los próximos requests que me hagas este número de usuario". El dato que se le pide al cliente que reenvie se llama "cookie", y en general está limitado a 4kb por cookie.
4) Como bien dijo Angel, existen distintas políticas de expiración de un cookie, lo que significa que existen estrategías para avisarle al cliente cuando debe dejar de enviar este dato adjuntado. Por ejemplo, se le puede pedir al cliente que envie una cookie durante un tiempo determinado (como durante dos horas, tres días, etc.). Se le puede pedir al cliente que envie una cookie para toda la eternidad. Es importante entender dos cosas: por un lado, el cliente puede decidir dejar de enviar la cookie, dado que el servidor no tiene control de lo que el cliente envía. Por otro lado, el servidor le puede pedir al cliente que deje de enviar una cookie.
5) Ahora si, con todo este conocimiento, nos metemos en los mecanismos "session" y "cookies" de varios frameworks. En general, "session" es un mecanismo a través del cual accedés a datos persistentes entre request y request. Lo importante a entender acá es que es una abstracción sobre cómo se persisten estos datos. Vos metés algo en la session, el framework hace magia y de repente vos podés sacar ese algo en los subsiguientes requests. Una cookie en cambio no es una abstracción en el sentido amplio de la palabra. Cuando metés algo en una cookie, sabés que va a parar al response para avisarle al cliente que cada vez que haga un request adjunte ese algo que metiste usando el mecanismo definido por el estándar, y de esa forma podés acceder a ese algo en los subsiguientes requests.
6) La diferencia entre session y cookies es que la session es una abstracción, y como tal existen diferentes estrategias para implementarla. Pongo algunos ejemplos para que se entienda la idea:
a) Se puede meter todo el contenido que metés en la sessión adentro de una cookie. Cuando metés algo en la session, el framework lo mete encodeado de alguna manera adentro de una cookie. Cuando buscas algo en la session el framework decodifica la cookie y te devuelve lo que estás buscando. Este es el default de rails, por ejemplo.
b) Se puede meter un identificador en una cookie y almacenar lo que metés en la session en un store externo asociado a ese identificador. El cliente envia el identificador en la cookie en los requests, con ese identificador accedes a los registros en el store externo y con eso podés meter y sacar cosas del store. Por ejemplo, puedo tener los contenidos de la session en una base de datos, en una tabla por ejemplo, y el identificador es el id del registro en donde estan guardados los contenidos de la session.
c) Se puede meter un identificador en una cookie y almacenar en memoria lo que metés en la sessión (con un hash, por ejemplo). Cuando viene un request, buscás con el identificador en el hash el contenido de la sesión.
7) Te recomiendo que busques información, ahora que tenés los conceptos, acerca de estas diferentes estrategias para terminar de entender cómo interactuan las cookies con la session y, sobre todo, que ventajas y desventajas tiene cada estrategia en si. Y sobre todo, las estrategías que puse son ejemplos. Son implementaciones bastante naives que tienen grandes desventajas; ponete a leer para entender cuáles son esas desventajas y como corregirlas ahora que tenés el conocimiento general de cómo funciona todo este tema.
Saludos!