First, you need to have the workflow plugin enabled. You can check for it by visiting the plugins page (Admin -> Plugins), or just looking for a "Workflow" link under the Admin menu.
The Workflow link takes you to the top level workflow customization page, which has three parts: Categories, Statuses, and Workflows. Generally, you want to work through these panels from left to right, depending on how much you want to change.
You are absolutely correct that there's no way to create a status from the page that actually lets you edit a workflow. Only statuses that were previously created are shown. You have to go back to the main workflow page and create your custom status first by click on "Customize Statuses", adding your new custom status to the appropriate category, and then editing your workflow to use the newly defined status as appropriate.