Is it possible to create a workflow to check the condition of a sales order ship to state (province in this case)?

Yes use the State/Province field of your condition builder