Wordpress create a new post status?
You can add custom post status' using the register_post_status function. Refer to create_initial_post_types() in http://core.trac.wordpress.org/browser/tags/3.2.1/wp-includes/post.php
Be warned however, that this is not integrated into the Wordpress backend UI.
Since WP 3.0, you can use the register_post_status() function ( http://hitchhackerguide.com/2011/02/12/register_post_status/ ) to add new statuses to a post type.
WP itself uses register_post_status() to register the default "published", "draft", etc. statuses on init using the create_initial_post_types() function in wp-includes/post.php ( http://hitchhackerguide.com/2011/02/11/create_initial_post_types/ ).
Look at the code in those links, and you can get an idea of how to use the function.
I hope that helps you get started!
You could write a plugin if you know how. You have to dig into the documentation or similar plugins like this one http://wordpress.org/extend/plugins/edit-flow/ or this one http://wordpress.org/extend/plugins/custom-post-type-ui/
With "Hooks, Actions and Filters" you can change the admin interface, see here http://codex.wordpress.org/Plugin_API
So far I've write just one simple plugin and I don't know the exact steps you have to follow to accomplish this...
Good luck!