Go to Administration -> Contacts, Deal statuses tab. Here you can add new statuses, modify or even delete existing ones. In order to modify an existing status just click on its name. You can change name, color, status and decide if it should be a default status.
Newly added statuses are not visible by default. You need to activate them for the particular project(s). To do so, go to Administration -> Projects -> Select the projects -> go to Deals tab, and then activate the statuses you want to use in the certain project(s). On the same tab, you may also add or edit deal categories