Make wp_dropdown_categories into a variable that persists until changed?

Just use the selected argument:

wp_dropdown_categories( array(
    'show_option_all' => 'All Deployments',
    'hierarchical' => true,
    'show_count' => true,
    'selected' => get_query_var( 'cat' ),
));

Update: Hook onto the tag_link filter & add the current category (if applicable):

add_filter( 'tag_link', 'wpse_71874_tag_link_category_context' );

function wpse_71874_tag_link_category_context( $link ) {
    if ( is_category() && $cat_id = get_queried_object_id() )
        $link = add_query_arg( 'cat', $cat_id, $link );
    return $link;
}