Oh, you know what? I just researched a bit more, and I think you might actually be right about it being a State machine anyway!
There's a very subtle difference. To really use the State pattern--and not State machine--I'd have to provide the state objects with the implementation.
In the case of C#, it'd probably be something like providing an Action to the state's constructor. In this way the Booking itself would provide the implementation, but the state object can determine what to do with it.