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?pagename=stores&state=$matches[1]','top');
Within your Template
Inside you template, get the query variable using this. 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.