It's clear how to create a new order status. System > Order Statuses > Create New Status
But how do you create a new state?
"processing", "complete", "new" are examples of the default Magento order state codes.
Open file app/code/core/Mage/Sales/etc/config.xml
and find node. Inside this node, add following.
<mystate translate="label">
<label>My State</label>
<statuses>
<mystatus default="1"/>
</statuses>
<visible_on_front>1</visible_on_front>
</mystate>
Note : I don't recommend to edit core files. But what you can do is, set this in your own module which is depends on Mage_Sales module.
you can add state by simply add xml code in your module config.xml
<global>
<sales>
<order>
<states>
<order_recieved translate="label">
<label>Order Recieved</label>
<statuses>
<order_recieved default="1"/>
</statuses>
<visible_on_front>1</visible_on_front>
</order_recieved>
</states>
</order>
</sales>
</global>
Also, you can create the status via System > Order Statuses > Create New Status, and then assign the status to a state (System > Order Statuses > Assing Status to State).