On bash 4.0 or newer, with readarray / mapfile available, the following serves as a terse and correct implementation:
for state in "${FIRST_ARRAY[@]}"; do
    readarray -t "ARRAY_$state" < <(search "$state" cities)
done
In bash 4.3, a safe, literal translation of your code is available:
for state in "${FIRST_ARRAY[@]}"; do
    readarray -t cities < <(search "$state" cities)
    # make "dest" a namevar -- an alias -- for your intended destination
    # skip to next state if current state name is invalid
    # otherwise we could be assigning to an utterly different "dest"
    declare -n dest="ARRAY_$state" || continue
    # assign to that namevar
    dest=( "$cities" )
    # and discard it
    unset -n dest
done
In bash 3.x, doing this safely requires some printf %q magic to prepare content to be parsed by eval:
for state in "${FIRST_ARRAY[@]}"; do
    # why this, and not array=( $cities )? Try a city with spaces in its name.
    # or look at what happens when you have a "city name" that's a wildcard.
    cities=( )
    while read -r city; do
        cities+=( "$city" )
    done < <(search "$state" cities)
    # generate eval-safe replacement for the cities array
    printf -v cities_str '%q ' "${cities[@]}"
    # extra paranoia: make sure we fail with a parse error rather than doing something
    # unexpected if the state name is not a valid shell variable
    printf -v eval_str 'ARRAY_%q=( %s )' "$state" "$cities_str"
    eval "$eval_str" # and evaluate that
done
The original question didn't provide an implementation of search to make answers testable. For this answer, I'm using the following:
search() {
  case $1 in
    NEWYORK) printf '%s\n' newyorkcity buffalo albany ;;
    CALIFORNIA) printf '%s\n' sanfrancisco paloalto losangeles ;;
    TEXAS) printf '%s\n' houston dallas austin ;;
  esac
}
With the above defined, results can be verified as follows:
$ declare -p ARRAY_NEWYORK ARRAY_CALIFORNIA ARRAY_TEXAS
declare -a ARRAY_NEWYORK='([0]="newyorkcity" [1]="buffalo" [2]="albany")'
declare -a ARRAY_CALIFORNIA='([0]="sanfrancisco" [1]="paloalto" [2]="losangeles")'
declare -a ARRAY_TEXAS='([0]="houston" [1]="dallas" [2]="austin")'