Edit Order Statuses

System > Localization > Order Statuses

Order Status Name: The wording you want to display.

After you have made your changes, click save button

Set default order status in System > Settings > Checkout

Almost all payment methods have default order status settings too in Extensions > Payments