This gives the code for creating a custom post type with all the necessary labels and even custom message support, and it gives the code for a custom taxonomy with that post type.