You are in luck, I had to do this for one of my projects. Here's a widget I made for a project where I had the same problem but I had 3 levels, Country->state->city
For countries that don't have states you can use administrative regions, but it's also trivial to adapt this to only 2 levels.
db.define_table('country',
    Field('name', length=128, requires=IS_NOT_EMPTY(), notnull=True, unique=True),
    Field('acronym', length=2, requires=IS_NOT_EMPTY()),
    format='%(name)s'
)
db.define_table('state',
    Field('name', length=128, requires=IS_NOT_EMPTY(), notnull=True),
    Field('acronym', 'string', requires=IS_NOT_EMPTY()),
    Field('country','reference country', requires=IS_IN_DB(db, db.country.id, '%(name)s'), represent=lambda x, row: db.country[x].name),
    format='%(name)s'
)
db.define_table('city',
    Field('name', length=128, requires=IS_NOT_EMPTY(), notnull=True),
    Field('state', 'reference state', requires=IS_IN_DB(db, db.state.id, '%(name)s'), represent=lambda x, row: db.state[x].name),
    format='%(name)s'
)
auth.settings.extra_fields['auth_user']= [
    Field('city','reference city', label=T('City'), requires=IS_IN_DB(db, db.city.id, '%(name)s'))
]
class LOCATION_SELECTS(DIV):
    """ A helper that essentially creates a div with the 3 selects used to choose a location """
    def __init__(self, *args, **attributes):
        if '_id' not in attributes:
            import random
            attributes['_id'] = 'ls' + str(random.random())[2:]
        def mk_sel_select(entities, selected, name):
            s = SELECT(_name=name)
            s.append(OPTION(T('Pick a %s' % name), _value=0))
            for entity in entities:
                if entity.id == selected:
                    s.append(OPTION(entity.name, _value=entity.id, _selected='selected'))
                else:
                    s.append(OPTION(entity.name, _value=entity.id))
            return s
        DIV.__init__(self, *args, **attributes)
        countries = db(db.country.id > 0).select(orderby=db.country.name)
        if 'initial_city' in attributes:
            sel_city = attributes['initial_city']
            rec_city =  db.city[sel_city]
            sel_state = rec_city.state
            sel_country = rec_city.state.country
            states = db(db.state.country == sel_country).select(orderby=db.state.name)
            cities = db(db.city.state == sel_state).select(orderby=db.city.name)
            self.components.append(mk_sel_select(countries, sel_country, 'country'))
            self.components.append(mk_sel_select(states, sel_state, 'state'))
            self.components.append(mk_sel_select(cities, sel_city, 'city'))
        else:
            self.components.append(SELECT(OPTION(T('Pick a country'), _value=0), *[OPTION(country.name,_value=country.id) for country in countries], _name='country'))
            self.components.append(SELECT(OPTION(T('Pick a region'), _value=0), _name='state', _disabled='true'))
            self.components.append(SELECT(OPTION(T('Pick a city'), _value=0), _name='city', _disabled='true'))
    def xml(self):
        return (DIV.xml(self) + 
            SCRIPT("""$(document).ready( function() {
                        var country_sel = $('#%(sid)s select[name="country"]');
                        var state_sel = $('#%(sid)s select[name="state"]');
                        var city_sel = $('#%(sid)s select[name="city"]');
                        var state_cache = new Object();
                        var city_cache = new Object();
                        var state_func = function(data) {
                            state_sel.children('option:gt(0)').remove();
                            $.each(data.states, function(key, val) {
                                state_sel.append('<option value="' + data.states[key].id + '">' + data.states[key].name + '</option>');
                            });
                            state_sel.removeAttr('disabled');                        
                        }
                        var city_func = function(data) {
                            city_sel.children('option:gt(0)').remove();
                            $.each(data.cities, function(key, val) {
                                city_sel.append('<option value="' + data.cities[key].id + '">' + data.cities[key].name + '</option>');
                            });
                            city_sel.removeAttr('disabled');
                        }
                        country_sel.change(function () {
                            var val = country_sel.val();
                            if (val === '0') {
                                state_sel.children('option:gt(0)').remove()
                                state_sel.attr('disabled', '');
                                city_sel.children('option:gt(0)').remove();
                                city_sel.attr('disabled', '');
                                return;
                            }
                            city_sel.children('option:gt(0)').remove();
                            city_sel.attr('disabled', '');
                            
                            if (val in state_cache) {
                                state_func(state_cache[val]);
                            } else {
                                $.getJSON('%(getstates)s' + '/' + encodeURIComponent(val), function(data) {
                                    state_cache[val] = data;
                                    state_func(data);
                                });
                            }
                        });
                        state_sel.change(function () {
                            var val = state_sel.val();
                            if (val === '0') {
                                city_sel.children('option:gt(0)').remove();
                                city_sel.attr('disabled', '');
                                return;
                            }
                            if (val in city_cache) {
                                city_func(city_cache[val]);
                            } else {
                                $.getJSON('%(getcities)s' + '/' + encodeURIComponent(val), function(data) {
                                        city_cache[val] = data;
                                        city_func(data);
                                });
                            }
                        });
                });
                """ % {'sid':self['_id'], 'getstates':URL('default', 'get_states.json'), 'getcities':URL('default', 'get_cities.json')} ).xml())
def city_widget(field, value):
    """ A widget for city fields that makes you put the country and state too """
    try:
        value = int(value)
        if value <= 0:
            raise ValueError()
        widget = LOCATION_SELECTS(initial_city=value)
    except (ValueError, TypeError) as e:
        widget = LOCATION_SELECTS()
    widget.components[-1]['requires'] = field.requires
    return widget
db.auth_user.city.widget = city_widget