Good database structure for scenario with orders that have a state and the state has a date
Since you already put order_state_id in your orders table why you don't put a timestamp or a datetime column along with it?  

When you update order_state_id to the desired state update the timestamp along with it.  

If you think that there is a high probability that your status list will expand over time then you may have a need to keep history of status changes for each order. In order to do that you'll need to throw out order_state_id and the timestamp from orders and create an association table like that will link orders with order_state :

orders_state_history
record_id (optional)
order_id  
state_id
timestamp/datetime