Semi complicated custom taxonomy question

Start with a tax_query to get posts with the 'categorie' taxonomy term you want. Assuming a custom query:

$tax_query_args = array(
    'tax_query' => array(
        array(
            'taxonomy' => 'categorie',
            'field' => 'slug',
            'terms' => array( 'costa' )
        ),
);
$tax_query = new WP_Query( $tax_query_args );

Then, step through that query, and use get_the_terms() to return the brand taxonomy terms for each post, and add them to an array:

$tax_query_brand_terms = array();

if ( $tax_query->have_posts() ) : while ( $tax_query->have_posts() ) : $tax_query->the_post();

    $post_brand_terms = get_the_terms( get_the_ID(), 'brand' );
    if ( is_array( $post_brand_terms ) ) {
        $tax_query_brand_terms = array_merge( $tax_query_brand_terms, $post_brand_terms );
    }

endwhile; endif;
wp_reset_postdata();

Now, the $tax_query_brand_terms array should be populated with all of the brand taxonomy terms for posts in the specified categorie taxonomy term.

If you want to wrap it in a function, allowing you to pass a categorie taxonomy term as a parameter:

function wpse63233_tax_query_brand_terms( $categorie = false ) {
    if ( false == $catgorie ) {
        return false;
    }
    // Also, put in some error checking here,
    // e.g. comparing $categorie against
    // get_terms( 'categorie' )

    // Query 'categorie' posts
    $tax_query_args = array(
        'tax_query' => array(
            array(
                'taxonomy' => 'categorie',
                'field' => 'slug',
                'terms' => array( $categorie )
            ),
    );
    $tax_query = new WP_Query( $tax_query_args );

    // Get 'brand' terms from all returned posts
    $tax_query_brand_terms = array();

    if ( $tax_query->have_posts() ) : while ( $tax_query->have_posts() ) : $tax_query->the_post();

        $post_brand_terms = get_the_terms( get_the_ID(), 'brand' );
        if ( is_array( $post_brand_terms ) ) {
            $tax_query_brand_terms = array_merge( $tax_query_brand_terms, $post_brand_terms );
        }

    endwhile; endif;
    wp_reset_postdata();

    // Return the array
    return $tax_query_brand_terms;
}