My rule is:
1) If you can, use a URL paramater to store state, because it provides the most predictable and scalable 'web behavior'
2) ..if that's not suitable, use a URL-based session, because it provides more predictable web behavior than cookie-sessions
3) ..if that's not suitable, use a cookie, because it scales easily
4) ..if that's not suitable, use a cookie based session, because, well.. nothing else worked
A cookie is stored by the client browser and sent back from the client to the server each time it requests a webpage fro the same cookie domain (normally the same server name or domain). A cookie can be set to live a short time, or a very long time (including forever).
A Session is server-side storage, which is generally stored in ram or on-disk on your server. Each time the same client comes back to the server, the server-side session storage is loaded/available. A unique URL paramater or cookie must be used to identify the client, so you can find his server-side session state.
Cookies are easier to scale across multiple web servers, because the client stores and re-produces the cookie each request, regardless of which server they are sent to in a load-balanced situation. Server-affinity load balancing can remedy this to a degree, but has it's own set of drawbacks. Sessions also usually impact server performance more, because the servers have to handle every session, wheras with cookies this work is offloaded to each client for himself.
Server Sessions are much more suitable for large result sets, as they don't need to be sent back and forth between the client and server each request.
In some situations, neither Sessions nor Cookies are a good answer, and URL paramaters or other methods are a better choice. In the web, we expect to be able to launch multiple browsers on the same website, and click "back" and "forward" often. Using Cookies or Sessions to store application state can create problems where the same operation can't be performed in two separate browser windows. In this case a URL paramater based state-mechanism may be more appropriate.
Hope that quick overview helped. Read the wikipedia pages on Session
for more information.