When dealing with the orders you actually have both status and state. status is the label you see against the order telling you, well it's status, but the state defines what actions can be performed against that order. You are probably only going to need to use a new status as the existing states cover most scenarios. You can add a new state using a data install script for your module:
<?php
$installer = $this;
// new status details
$data = array(
array('status' => 'new_status', 'label' => 'New Status')
);
// add new status to the relevant table
$installer->getConnection()->insertArray(
$installer->getTable('sales/order_status'),
array('status', 'label'),
$data
);
// data associating new status with existing state
$data = array(
array('status' => 'new_status', 'state' => 'holded', 'is_default' => 0)
);
// add association data to the relevant table
$installer->getConnection()->insertArray(
$installer->getTable('sales/order_status_state'),
array('status', 'state', 'is_default'),
$data
);
When you have done the above to create each new order status you will probably want to do something along the lines of use save observers on invoice/shipment creation to modify the order state. You can do this very simply once you have the order object using:
$order->setState($state, $status, $comment, $notifycustomer)->save();
$state should be the order state, $status is optional and can be the new status you created, but it can also be true to use the default status for the state. $comment is optional and should be any comment you want to add to the order, and $notifycustomer is optional and should be true or false (default) according to whether you want to notify the customer about the status change.
