How can I populate a select element with terms from a custom taxonomy and filter post results?

Are you familiar with jQuery? You’ll want to post the term to a admin-ajax, and use the response to populate the second select.

Here is the codex documentation:
http://codex.wordpress.org/AJAX_in_Plugins

A loose example for your situation:

$first_term = $('#states');
$name = $first_term.children('option:selected').text();
    var data = {
            action: 'tag_slug',
            slug: $slug
        };

    var ajaxurl="wp-admin/admin-ajax.php";
    $.post(ajaxurl, data, function(response) {
        $('#city').empty().append(response);
    });

You would build the options in a similar way as you have show in your AJAX response callback, so that that is what is returned and is what is appended to the City select.

Note the “Ajax on the Viewer-Facing Side” section of the above codex link to make sure it works for non-loggedin users.