Recently we had a client who wanted the ability to add new taxonomy terms from the front end of their site. This turned out to be pretty easy using the following code.
//here we take the term name from the client and use the wp_insert_terms() function to add this term to our 'taxonomy'
$new_term = wp_insert_term(
$_POST['new_term'], // the term
'taxonomy', // the taxonomy
'slug' => sanitize_title_with_dashes($_POST['new_term'], '', 'save') //this function will clean and save our term name as a url safe slug
//this part is not needed to create the term, but in our use case this new term is also being applied to a post
$tag = array( $new_term['term_id'] );
wp_set_post_terms( $post_id, $tag, 'taxonomy' );
Obviously this is just the bare minimum required. You are on your own for validation and such.