New order statuses can be created under: Configuration > Orders settings > Order Status Codes.

New statuses will automatically show up in the "Status" drop down list. This feature allows you to add custom statuses to an order that may be specific to your store.

The following short video will show you how to create a new code.