Order States: These are fixed order states which magento uses internally to maintain order flow and show various order actions. The fixed states are New, Processing, Pending Payment, Payment Review, On Hold, Complete, Cancelled, Closed.
Order status are not displayed anywhere, but are used by magento internally.
Order Status: These states used for display purposes. Each states belongs a order status, and multiple states can belong to a single order status. We can also added new states from System -> Manage Order Statuses
Order Status are defined in sales/config.xml in global -> sales -> order -> states, we add new order states from here as well.
Order states are stored in table ‘sales_order_status’
The table ‘sales_order_status’ only has label and code for each order status.
We have another table ‘sales_order_status_label’ which defines order label per store, so different stores can have different status labels
Another table ‘sales_order_status_state’ stores the association of order status to order state.