¿Cómo actualizar el menú desplegable sin actualizar la página?

Usa jQuery Ajax

tuarchivo.php

<select id="location" onchange="getState(this.value)" name="location" class='form-control'>
<option value="0">Select location</option>
    <?php
        $query = mysql_query("select * from city");
            while($row = mysql_fetch_assoc($query))
            {
                echo '<option value="'.$row['cityid'].'">'.$row['cityname']. '</option>';
            }
    ?>
</select>

<select id="state">

</select>

Script JQuery

function getState(city_id)
{
    var html = $.ajax({
        type: "POST",
        url: "path/to/ajax/my_ajax.php",
        data: "city_id=" +city_id,
        async: false
    }).responseText;
    if(html){
        $("#state").html(html);
    }
}

AJAX.php

$query = mysql_query("select * from state where city_id=".$_REQUEST['city_id']);
            while($row = mysql_fetch_assoc($query))
            {
                echo '<option value="'.$row['state_id'].'">'.$row['state_name']. '</option>';
            }