State machines can reduce complexity of workflows when there are multiple loops and branching or logic when the workflow must "react" to answers supplied by users. This would be an event-driven workflow.
In what circumstances have you elected to use a state machine and what type of pain did reduce in terms of time and complexity?
State machines are really nice for event-driven code. You can't use loops and branches if your code is being invoked as a response to some event. You'll have to use a state machine instead, feed the events into it to change the state, and have the event handler react according to the machine's current state.
State machine workflows are meant to be used when there is no predefined steps through workflow completion. Take a look into this definition (from State Machine Workflows in Windows Workflow Foundation)
A workflow is a defined process consisting out of several steps which implement the needed behavior. There are basically two kinds of workflows: sequential workflows and state machine workflows. In sequential workflows all decisions to progress in the workflow are taken by the workflow itself. There’s a well defined start and well defined end. Between there’s a flow consisting of branches and loops to direct the flow. This means the workflow is in control.
With state machine workflows there’s no real predefined path of all steps to undertake for a certain solution. State machines take another approach. They wait for events to happen and based on these events they change their state. State machines are used when the decisions are coming in from an external application and are unpredictable. So especially when there’s user interaction needed a state machine is a more convenient solution.
State machine and linear workflow are sufficiently different problem spaces to be unrelated in terms of application development.
The process being modelled drives the approach, you use a state machine for a process that has a number of states in which the unit of work can exist and for which there is a potentially non-linear progression through the states. Where a clearly linear process exists, one for which there is no significant backtracking then a linear workflow (or sequential workflow) would be used.