Rewrite rule for a query string

Try this code:

function geotags_add_rewrite_rules($wp_rewrite_rules) {
    global $wp_rewrite;

    $rule_key = '%cityid%';
    $url_pattern = '([^/]+)';
    $query_string = 'cityid=';

    $wp_rewrite->add_rewrite_tag($rule_key, $url_pattern, $query_string);

    $url_structure = $wp_rewrite->root . "cityid/$rule_key/";
    $rewrite_rules = $wp_rewrite->generate_rewrite_rules($url_structure);

    $wp_rewrite_rules = $rewrite_rules + $wp_rewrite_rules;
    return $wp_rewrite_rules;
}

add_filter('rewrite_rules_array', 'geotags_add_rewrite_rules');

function geotags_add_query_var($query_vars) {
    array_push($query_vars, 'cityid');
    return $query_vars;
}

add_filter('query_vars','geotags_add_query_var');

NOTE: Remember to save permalinks so your new rule is picked up by WP.