How do you create a new order state for an order status to be assigned to?

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>

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.

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).