To create a new order status in your store, do the following:
Click on the menu Configuration > Store Settings > Statuses > Order Statuses. You will now see a new screen called "ORDER STATUS LIST".
To create your new order status, click on the "plus icon" in the top right hand corner of your screen. Add a name for your order status and save it.