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