Add a css class to a taxonomy permalink

The filter you are looking for is term_links-$taxonomy, where $taxonomy is the taxonomy name. This will filter the $term_links links array before outputting by the_terms():

add_filter('term_links-cities', 'ad_filter_links');

function ad_filter_links($term_links) {
    foreach ($term_links as $term_link) {
        $term_link = str_replace('<a ', '<a class="fancybox"', $term_link);
    }
    return $term_links;
}