Passing form inputs into multi-taxonomy query

You mention that with your first attempt you get the URL http://sitename.com/?brand=22 which is correct as you’ve used a get method, but you don’t say what code you’re using for the query.

Personally I use this for my form and would agree with wdalhaj to use post instead of get

<form id="brandsearch" method="post" action="">
  <select name="brand" id="brand">
    <option value="">All</option>
<?php
$theterms = get_terms('brand', 'orderby=name');
foreach ($theterms AS $term) :
    echo "<option value="".$term->slug.""".($_POST['brand'] == $term->slug ? ' selected="selected"' : '').">".$term->name."</option>\n";
endforeach;
?>
  </select>
</form>

and then for building the query

$myquery['post_type'] = 'custom-post-name';
$myquery['posts_per_page'] = -1; // only used if you want all results on one page
$myquery['tax_query'] = array();

if (!empty($_POST['brand'])) :
    $brand = $_POST['brand'];
    $myquery['tax_query'][] = array(
        'taxonomy' => 'brand',
        'terms' => array($brand),
        'field' => 'slug',
    );
endif;

query_posts($myquery);

You can put the form into a standard page using a page template or a shortcode (see http://codex.wordpress.org/Function_Reference/add_shortcode) but you’ll be best off creating a page template for your search query and results.