Making a form for user to add new custom post with custom taxonomies and custom fields

To list the options for a custom taxonomy you need to query the taxonomy terms. To do that you use get_terms() http://codex.wordpress.org/Function_Reference/get_terms

// We are assuming color is the name of the taxonomy
$colors = get_terms( 'color', array(
    'orderby'    => 'name',
    'hide_empty' => 0
));

// Now loop through the colors and spit out the checkbox
// with the name of the color as well as the value of the term_id

foreach($colors as $color){ 
....

On the server side for handling the submission (once you get the form correct) you can use wp_set_post_terms() http://codex.wordpress.org/Function_Reference/wp_set_post_terms