First you have to define the new states you want to add. To do that you can create a new module with a class that inherits from sale.order. Copy the existing states that are defined in the sale module (sale.py line 189) and add your new state to the selection field. The result should look something like this:

class Sale_order(osv.Model):

    _inherit = 'sale.order'

    _columns = {
        'state': fields.selection([
            ('draft', 'Draft Quotation'),
            ('my_new_state', 'My New State'),
            ('sent', 'Quotation Sent'),
            ('cancel', 'Cancelled'),
            ('waiting_date', 'Waiting Schedule'),
            ('progress', 'Sales Order'),
            ('manual', 'Sale to Invoice'),
            ('invoice_except', 'Invoice Exception'),
            ('done', 'Done'),
            ], 'Status', readonly=True, track_visibility='onchange',
            help="Gives the status of the quotation or sales order. \nThe exception status is automatically set when a cancel operation occurs in the processing of a document linked to the sales order. \nThe 'Waiting Schedule' status is set when the invoice is confirmed but waiting for the scheduler to run on the order date.", select=True),
    }

To actually get the new state to show up in the form view's progress bar, you need to inherit and customize the sale order's form view and add your new state to the comma-separated list inside the statusbar_visible attribute:

<openerp>
    <data>
        <!-- Inherit the sale order model's form view and customize -->
        <record id="sale_form_view" model="ir.ui.view">
            <field name="name">sale.order.form.inherit</field>
            <field name="model">sale.order</field>
            <field name="inherit_id" ref="sale.view_order_form"/>
            <field name="arch" type="xml">
                <!-- Statusbar widget should also contain the new status -->
                <field name="state" position="replace">
                    <field name="state" widget="statusbar" statusbar_visible="draft,my_new_state,sent,invoiced,done" statusbar_colors='{"invoice_except":"red","waiting_date":"blue"}'/>
                </field>
            </field>
        </record>
    </data>
</openerp>

After this you should be able to see the new state in your progress bar:

There's still no functionality to advance to the new state though. To sort this out we will use workflows. The documentation defines workflows as follows:

A workflow is a directed graph where the nodes are called "activities" and the arcs are called "transitions".

Activities define work that should be done within the OpenERP server, such as changing the state of some records, or sending emails.

Transitions control how the workflow progresses from activity to activity.

If you take a look at the workflow of the sale module (sale_workflow.xml) you'll notice both the activities and the transitions are defined using simple <record> tags. You'll also note that there are already activities for the existing states, e.g. act_draft and act_sent. What we need to do is add a new activity for our new state to our own module. The workflow XML is usually put into a separate XML file, like this:

<openerp>
    <data>
        <!-- Create new activity for the new state -->
        <record id="act_my_new_state" model="workflow.activity">
            <field name="wkf_id" ref="sale.wkf_sale"/>
            <field name="name">my_new_state</field>
            <field name="kind">function</field>
            <field name="action">action_my_new_function()</field>
        </record>
    </data>
</openerp>

That code tells OpenERP that once a user arrives to this activity (which is a part of an existing sale.wkf_sale workflow) via some transition, a python function called action_my_new_function() should be executed. But before defining the function itself, let's finish the rest of the XML. We now need to define the transitions between different states.

Let's say we want to be able to progress from Draft Quotation to My New State, from My New State to Quotation Sent, and also go back from Quotation Sent to My New State. For that we need the following transitions:

<openerp>
    <data>
        <!-- Create new activity for the new state -->
        <record id="act_my_new_state" model="workflow.activity">
            <field name="wkf_id" ref="sale.wkf_sale"/>
            <field name="name">my_new_state</field>
            <field name="kind">function</field>
            <field name="action">action_my_new_function()</field>
        </record>

        <!-- Create transitions -->
        <!-- From Draft to new state -->
        <record id="trans_draft_my_new_state" model="workflow.transition">
            <field name="act_from" ref="sale.act_draft"/>
            <field name="act_to" ref="act_my_new_state"/>
            <field name="signal">signal_my_new_state_forward</field>
        </record>    

        <!-- From new state to Quotation Sent -->
        <record id="trans_new_state_sent" model="workflow.transition">
            <field name="act_from" ref="act_my_new_state"/>
            <field name="act_to" ref="sale.act_sent"/>
            <field name="signal">signal_quotation_sent</field>
        </record>

        <!-- From Quotation Sent back to new state -->
        <record id="trans_sent_new_state" model="workflow.transition">
            <field name="act_from" ref="sale.act_sent"/>
            <field name="act_to" ref="act_my_new_state"/>
            <field name="signal">signal_my_new_state_backward</field>
        </record>  

    </data>
</openerp>

Note the act_from and act_to fields: we have only defined one activity inside our module, we are mostly referencing existing activities that are defined inside the sale module.

The signals tell what user inputs are used to trigger the transition, In our example we'll use the press of a button as a trigger. Let's add new buttons to the form view definition. Note the states attributes, they limit in which states the button will be visible. The name attribute of the button matches the signal defined in the workflow and thus triggers the transition to a specific activity.

<?xml version="1.0" encoding="UTF-8"?>
<openerp>
    <data>
        <!-- Inherit the sale order model's form view and customize -->
        <record id="sale_form_view" model="ir.ui.view">
            <field name="name">sale.order.form.inherit</field>
            <field name="model">sale.order</field>
            <field name="inherit_id" ref="sale.view_order_form"/>
            <field name="arch" type="xml">

                <!-- Statusbar widget should also contain the new statuses -->
                <field name="state" position="replace">
                    <field name="state" widget="statusbar" statusbar_visible="draft,my_new_state,sent,invoiced,done" statusbar_colors='{"invoice_except":"red","waiting_date":"blue"}'/>
                </field>

                <field name="state" position="before">
                    <!-- From draft to new state -->
                    <button string="Send to new state" type="workflow" name="signal_my_new_state_forward" states="draft" class="oe_highlight"/>

                    <!-- From new state to Quotation Sent -->
                    <button string="Mark as sent" type="workflow" name="signal_quotation_sent" states="my_new_state" class="oe_highlight"/> 

                    <!-- From Quotation Sent back to new state -->
                    <button string="Back to new state" type="workflow"  name="signal_my_new_state_backward" states="sent" class="oe_highlight"/>
                </field>
            </field>
        </record>
    </data>
</openerp>

Now if we create a new quotation and save it, we can see one of the new buttons.

The rest of the buttons appear when we progress in the states. If you click the new button nothing happens because we have not yet written the Python code that actually changes the sale order's state on button click. This requires only little code that is put inside our sale order subclass. Note that the function name is the same as in the action of our new activity, i.e. action_my_new_function()

def action_my_new_function(self, cr, uid, ids, context=None):
    res = self.write(cr, uid, ids, {'state': 'my_new_state'}, context=context)    
    return res

And that's it, now you should be able to jump between the states. There's a lot of fine-tuning you can still do after that, but hopefully this gives the basic idea of how states, transitions and activities work.

You will likely need to also override and customize some of the existing buttons defined in the sale module (e.g. to get the Print button to show up also in the new state).

You may also run into view inheritance issues if you are using many different modules that customize the sale views. One way to deal with the issue is this.