Create a Page Template

Add a new page and give it the slug stores

Add A Public Query Variable

add_filter('query_vars', 'add_state_var', 0, 1);
function add_state_var($vars){
    $vars[] = 'state';
    return $vars;
}

Add a rewrite rule

This will direct your request to your stores page.

add_rewrite_rule('^stores/([^/]*)/?','index.php?post_type=page&name=stores&state=$matches[1]','top');

Within your Template

You can access your state variable as follows:

 $state = get_query_var('state');

Flush your Permalinks

Visit Settings->Permalinks to flush your permalinks and add your rewrite rule to the stack.