As with all sorts of thing, "it depends".
There are different solutions and approaches.
As mentioned, there's the concept of a centralized store for session state (database, memcached, shared file system, etc.).
There are also cluster wide caching systems available that make local data available to all of the machines in the cluster. Conceptually it's similar to the centralized session state store, but this data isn't persistent. Rather it lives within the individual nodes and is replicated using some mechanism provided by your provider.
Another method is server pinning. When a client hits the cluster the first time, some mechanism (typically a load balancer fronting the cluster) pins the client to a specific server. In a typical client lifespan, that client will spend their entire time on a single machine.
For the failover mechanism, each machine of the cluster is paired with another machine, and so any session changes are shared with the paired machine. Should the clients pinned machine encounter an issue, the client will hit another machine. At this point, perhaps due to cookies, the new machine sees that it's not the original machine for the client, so it pings both the original machine, and the paired machine for the clients session data.
At that point the client may well be pinned to the new machine.
Different platforms do it in different ways, including having no session state at all.