From a runtime point of view it is advantageous to have stateless services. Statelessness - from a conceptual point of view -- means that the service does not "remember" state between consecutive invocations. Of course, the service may still store information in the DB backend. The important point, however, is that this state is not within the service instance or the service volatile memory.
Clearly, stateless services do scale better: Additional instances of the service can be fired up to cope with increased load. They can also deal better with failover situations. A client request may be routed to an alternative instance transparently when the original instance goes down.
However, sometimes stateful services do make sense from a modelling perspective. Nicolai Josuttis, for example, describes a shopping cart service. For this type of service, a client would expect to successively call operations to add new items.
A stateful service may be implemented as a stateless service: either by sending all relevant information (eg the shopping cart contents) with every request or by sending a session ID with every request and keeping the shopping cart contents in the DB. Or a "real" stateful service keeps the shopping cart state in memory - this requires session affinity: ie, each successive request by a given client must be routed to the same service instance. When this instance goes down, the user must start their shopping trip all over again -- possibly an acceptable tradeoff in an eCommerce application. Nicolai Josuttis works out the associated tradeoffs (state in frontend, state in service, state in backend) really nicely in his book (p.195).