Statefulness is not necessarily a bad thing, but you need to understand the difference between stateful and stateless apps. In short, stateful apps maintain information about the current session, and stateless apps do not. Information stored permanently as part of a user account may or may not be stored in a session, but storing information related to a user account does not by itself make the application stateful. Statefulness requires that the server maintain information about the current user's session beyond what the client browser is maintaining. For instance, a client could authenticate and be given a JSESSIONID cookie, which it then sends to the server with each request. If the server starts storing stuff in the application's session scope based on this JSESSIONID, it becomes stateful.
Statefulness on the server
On the server, a stateful app saves state information about current users. This approach generally involves using cookies to identify the user's system so that state can be maintained on the server between requests. Sessions may or may not be authenticated, depending on the context of the application. Stateful server apps offer the advantage of caching user state information on the server, speeding up lookups and page response time. On the down side, storing information in session scope is expensive, and at scale it becomes very resource intensive. It also creates a potential attack vector for hackers to try and hijack session identifiers and steal user sessions. Stateful server apps also have the challenge of protecting user sessions against unexpected service interruptions, e.g. a server failure. A common solution to this problem is to cluster sessions across a cluster of server machines, but again, at scale it quickly becomes impractical to cluster all sessions across all machines.
Statefulness on the client
Tokens v. cookies
Cookies act as identifiers for client devices/browsers. They can be used to store all manner of things, but generally they store some form of identifier, like CFID/CFTOKEN in CFML apps. Cookies can be set to live in the user's browser for a long time, making it possible to do things like maintain authentication on an app between browser sessions. Cookies can also be set to memory-only so they expire when a user closes the browser.
Tokens are generally some kind of identifying information about the user that are generated on the server ( using encryption to scramble the information ), passed to the client, and returned to the server with the subsequent request. They may be passed in the header of the request and response, which is a common pattern in single page applications. Ideally, each request/response results in the generation of a new token, so tokens can't be intercepted and used later by an attacker.
Single Page Apps and client state
With SPAs, state information is loaded into the client browser and maintained there. When the state changes, e.g. you post an update to your social media account, the client relays that new transaction to the server. In this case, the server saves that update to a persistent data store like a database, and relays whatever information back to the client that it needs to synchronize with the server based on the update (e.g. an ID for the update ).
Note that this pattern of storing state on the client offers advantages for online/offline experiences in that you can be disconnected from the server while still having a somewhat usable application. Twitter is a good example of this case, where you can review anything loaded client side in your Twitter feed even if you are disconnected from the Twitter server app. This pattern also creates complexity in synchronization between server and client, which is a whole subject of its own. The complexities of the solution are a tradeoff for being able to maintain state on the client.
Statefulness on the client makes web apps feel and behave more like traditional desktop apps. Unlike desktop apps, you will typically not have all of your account information loaded into your client session in a browser. Doing so would in many cases be impractical and produce bad experiences. Can you imagine trying to load an entire Gmail box into the browser? Instead, the client maintains information like what label/folder you are looking at and where in the list of emails in that folder you are looking. Balancing what state information to maintain and what to request as needed is another engineering challenge of this pattern, and again, it represents a tradeoff between practicality and providing good user experiences.
Shopping carts and the like
As for specifics like shopping carts, it really depends on the solution. A shopping cart may be stored in a database on the server, it may be stored only in session scope on the server, or it may even be stored in the client. Amazon has persistent shopping carts for logged in users, and "temporary" carts for anonymous users, though these carts are persistent to some extent.
When you talk about something like Google, which is really a bunch of different applications living under the same brand, they probably do not share a common architecture, and each is built in the way that best meets the needs of its users. If you want to learn how a site is built, open the developer tools in your browser and look at it. Check for cookies, watch network traffic, and see how it runs.
Sorry if this answer rambles a bit, but statefulness is a complex subject.