Los datos de sesión se almacenan en el servidor, a diferencia de las cookies que son almacenadas en el cliente. En el caso de sesiones, lo único que "guarda" el cliente es el id de sesión (que el servidor tomará para poder leer los datos de la sesión correspondientes), y ese id necesita ser propagado a lo largo de la sesión de un visitante, ya sea por una cookie (sí, un archivo que se guarda en el cliente conteniendo sólo el id de sesión activo) o por la URL.
En cambio, las cookies son pequeños archivos individuales guardados todos en el cliente.
Hay que resaltar que una cookie vive por el tiempo que el script "creador" haya definido, mientras que el id de una sesión guardado en una cookie (con una configuración base del servidor PHP) permanece en el cliente sólo mientras este no termine la sesión de visita (no cierre el navegador).
Sabiendo eso ya puedes deducir cuál deberías usar, no?
