To add New Status in magento admin panel, you need to write your own custom module , then in your config.xml file write the below code to add new Status

 
<config>
    <global>
        <sales>
            <order>
                <statuses>
                    <custom_status translate="label"><label><![CDATA[Custom Status]]></label></custom_status>
                </statuses>
                <states>
                    <new><!-- order state where you want to assign your custom status e.g:- New, Onhold, Canceld etc--> 
                       <statuses> 
                           <custom_status/> 
                       </statuses>
                    </new>
                </states>
            </order>
        </sales>
    </global>
</config>

It will work upto 1.4.2 , But in Magento 1.5.0 or above there is Special Option to do this. To make own Custom status above magento 1.5 version go to System->Order Statuses. Then Click on Create New Status. After creating new status click on Assign Status to State to assign that status