How to properly rewrite url by custom var

So, first off, never flush rewrite rules on every page load. Better to do it on plugin activation one time.

Step 1: add the rewrite rule:

add_action( 'init', 'wpse26555_add_rewrite' );
function wpse26555_add_rewrite()
{
    // You should probably rewrite to index.php instead of shop.php?
    add_rewrite_rule( '/shop/brand/([^/]+)/?$', 'index.php?brand=$matches[1]', 'top' );
}

Step 2: add the query var

add_filter( 'query_vars', 'wpse26555_add_vars' );
function wpse26555_add_vars( $vars )
{
    $vars[] = 'brand';
    return $vars;
}

Then flush on plugin activation (because something like this should probably be in a plugin file).

<?php    
// Somewhere in your plugin's main file    
register_activation_hook( __FILE__, 'wpse26555_activation' );
function wpse26555_activation()
{
        // Add the rule first
        wpse26555_add_rewrite();
        // Then flush rewrite rules
        flush_rewrite_rules();
}

Then on the front end you can do something like this:

if( $brand = get_query_var( 'brand' ) )
{
    // Do stuff with $brand here

}

Maybe a better strategy would be to rewrite brand to a specific page? Or maybe brand could be some sort of custom taxonomy?

You’ll have to test the above code, it was off the top of my head, but it should work or at least get you started