When you design your service to be stateless, you are making it treat each new request as an independent event. No session is stored, nor information about the connecting clients. 1
This removes the need for a specific client to stay connected to a specific server, and instead of a session with multiple steps between a client and a single server you get multiple pairs of request-response traffic between a client and multiple service instances.
The main benefit of this is that as traffic grows, you can just add service instances and servers to handle the load. It doesn't matter where a specific client call ends up, since you don't need to keep track of it.
Stateless services are more common among RESTful web services than among SOAP based web services, but there is no specific technical reason for this.