Monads are mostly a popular pattern in Haskell because encapsulating side effects within monads allows the type system to enforce their proper usage. They're not necessary for immutability or state management in general. It's just a way to enforce discipline more than anything.

The way immutability is implemented is using persistent data structures. The idea is that you do structural sharing for the common data when creating changes, so you don't have to pay the price of a full copy of the data structure. In terms of performance, this approach works pretty well in most cases. It's more expensive than direct mutation, but far cheaper than a deep copy making it a good compromise for the general case.