What does maintaining state in a clustered environment mean? How is it implemented by the application server? How is the information in the session persisted/updated/propogated across clusters or machine boundaries?

In a clustered environment, the same application will exist in more than one machine. Since it is done for load balancing, you don't know the next request will go to which machine. What I mean by saying this is, the first page P1 may come from machine A, but the next page P2 may come from machine B. But the client should be un-aware of which page is coming from which machine.
If these pages are dependent i.e. given some events or input in P1 results to P2, then the information in P1 should be available in P2 also.

It is achieved through persisting the session information, mostly to an RDBMS. Whenever any machine requires read/add/update/delete/propagate the session info, it will use the database.
The application server provides provision for persisting the session information to the database and if selected, creates the required the table structure.

Does that mean that, stateful EJBs are going to be created in multiple machines(which support the service) in a cluster ?

Hi

This is a interesting read on how Weblogic acheives state management in a cluster

http://e-docs.bea.com/wls/docs61/cluster/object.html#1006807

Hrishi