I'd say store the state somewhere on the server and correlate it to the user's session. While a cookie could ostensibly be an equal place to store things, if you consider security and data size, keeping as much data on the server as possible becomes a good thing.
For example, in a public terminal setting, would it be OK for someone to look at the contents of the cookie and see the list? If so, cookie's fine; if not, you'll just want an ID that links the user to the data. Doing that would also allow you to ensure the user is authenticated to the site in order to get to that data rather than storing everything on the machine - they'd need some form of credentials as well as the session identifier.
From a size perspective, sure, you're not going to be too concerned about a 4K cookie or something for a browser/broadband user, but if one of your targets is to allow a mobile phone or BlackBerry (not on 3G) to connect and have a snappy experience (and not get billed for the data), minimizing the amount of data getting passed to the client will be key.
The server storage also gives you some flexibility mentioned in some of the other answers - the user can save their cart on one machine and resume working with it on another; you can tie the cart to some form of credentials (rather than a transient session) and persist the cart long after the user has cleared their cookies; you get a little more in the way of fault tolerance - if the user's browser crashes, the site still has the data safe and sound.
If fault tolerance is important, you'll need some sort of persistent store like a database. If not, in application memory is probably fine, but you'll lose data if the app restarts. If you're in a farm environment, the store has to be centrally accessible, so you're again looking at a database.
Whether you choose to key by transient session or by credentials is going to depend on whether the users can save their data and come back later to get it. Transient session will eventually get cleaned up as "abandoned," and maybe that's OK. Tying to a user profile will let the user keep their data and explicitly abandon it. Either way, I'd make use of some sort of backing store like a database for fault tolerance and central accessibility. (Or maybe I'm overengineering the solution?)