how do you handle stateful services in a stateless world

We're moving towards more stateless microservices, and that's great for scaling. But some services just have to keep state, right? Like, for real-time session data or when you have a complicated workflow. How are other people handling this? Are you hooking up separate databases to each service, using external state stores such as Redis or ZooKeeper, or maybe a mix of both? What problems have you run into with those choices?