Adding Variables to post query

As toscho said, you can modify the query in the pre_get_posts hook. That hook gets the query object passed as an argument, so you don’t have to read a global variable.

add_action( 'pre_get_posts', 'wpse12692_pre_get_posts' ); 
function wpse12692_pre_get_posts( &$wp_query )
{
    if( isset( $_SESSION['size'] ) && $_SESSION['size'] != 'all' )
    {
        $wp_query->query_vars['meta_query'] = array(
            'key' => 'cc_size',
            'value' => $_SESSION['size'],
        );
    }

    if( isset( $_SESSION['gender'] ) && $_SESSION['gender'] != 'all' )
    {
        $wp_query->query_vars['meta_query'] = array(
            'key' => 'cc_gender',
            'value' => $_SESSION['gender'],
        );
    }

    $wp_query->query_vars['orderby'] = 'post-title';
    // The next line is redundant, get_query_vars reads it from the global $wp_query object
    $wp_query->query_vars['paged'] = get_query_var('paged');
}

I see that your query depends on session variables. This can make it harder to forward a link to a page to someone else. Have you considered putting this in the URL and reading it from there? You can do that by creating extra rewrite rules.