Best way to apply versioning to State object-oriented design pattern?

I think you're making a mistake. A lot of times, this "mixed fleet" issue is going to be a feature, not a bug. In addition, this notion of "version" that you want to add creates complexity and restrictions, but adds very little value.

I think you just need to change your idea of what a state is. It's not "a step in the workflow". It's the entire remainder workflow process. That remaining process may involve multiple steps or it may not, but it's up to the state implementation to decide.

In a typical implementation of this kind of workflow system, there is a persisted "current state". When an event occurs, the current state is read from the DB and hydrated somehow into an implementation object. A handler in that object is then called to perform the appropriate action, and optionally return a new current state definition to be persisted.

The key to making a system like this comprehensible and maintainable is the design of the persisted state representation. This representation is the language that a state implementation uses to define what happens next. That language should be expressive enough to define any remaining process that might be necessary, and also simple, straightforward, and unambiguous, so that there is no confusion about how the serialized definition of "what happens next" turns into an implementation.

Your version idea ruins the "simple, straightforward" part, making it more difficult to figure out what's going to happen next in any workflow.

To make this concrete, lets consider your example...

In version 1, the start state transitions to the "RetrieveAndPublishFile" state. That state then transitions to the "PublishFileData" state. See how the name reflects the whole remainder of the process?

In version 2, you change the "RetrieveAndPublishFile" implementation so that it transitions to "CleanPiiAndPublish" instead of "PublishFileData". The "CleanPiiAndPublish" state cleans out the PII and then transitions to the "PublishFileData" state that you already have.

State pattern is not about to add new step into behaviour, it is about change the whole behaviour without adding new steps. As wiki says about State pattern:

The state pattern is a behavioral software design pattern that allows an object to alter its behavior when its internal state changes. This pattern is close to the concept of finite-state machines.

So if you have the following methods in State:

public interface IState
{
    void Run();

    void Swim();

    void Fly();

    IState GetNextState();
}

Then if you will add new method in the above interface, then you will need to add this new method in all concrete states. And that what you do not want to do.

If you want to add new step or behavior, then Decorator pattern can be used. As wiki says about decorator pattern:

In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other objects from the same class. The decorator pattern is often useful for adhering to the Single Responsibility Principle, as it allows functionality to be divided between classes with unique areas of concern. Decorator use can be more efficient than subclassing, because an object's behavior can be augmented without defining an entirely new object.

So it looks like Decorator pattern is better fit for your requirements.

Keeps state machine implementations fully isolated, but at the cost of an explosion of classes.

yeah, if you add new step, then it is better to add new class. Yeah, the cost is an explosion of classes. On the other hand, your classes will have:

• single responsibility
• great separation of concerns
• your class will be smaller and it allows to be unit tested very well