Well Haskell can still "stateless" in some sense, even if your program seems to take advantage of state. The State monad (and other monads), for example, just facilitate a bit of clever syntax to sneak computational context, which can include state, into the lambda calculus. The IO and STM monads (which deal with side effects) are a bit different, and can introduce true state into a program (with a bit of cleverness to make the existence of state mesh well with the lambda calculus).

No, it is indeed stateless. The fact that it represents state is proof of that. FP uses representations for things instead of the real things. For instance, OO purposefully causes changes in RAM to make things happen, where in FP changes in RAM are incidental and the programmer need not manage them. So it is stateless because you program indirectly by using these conceptual representations that are free of implementation.