How to list custom fields as headers and list all pages sharing that custom field under it?

What you want to do is create a variable that keeps track of the ‘current’ state, then for each post in the loop check if its state is the same as the current state. If it is not then output it and update the current state to the new state. This will have the effect of only outputting the state name in front of the first post with that state.

if ( $the_query->have_posts() ) :
    /**
     * Create the variable to keep track of the current State in the loop.
     */
    $current_state = null;

    echo '<ul>';
        while( $the_query->have_posts() ) : $the_query->the_post();
            $state = get_field( 'state_full' );

            /**
             * If the state of the current post is different to the current state
             * then output the new state and update the current state.
             */
            if ( $state !== $current_state ) {
                echo '<li><strong>' . $state . '</strong></li>';
                $current_state = $state;
            }

            echo '<li><a href="' . get_the_permalink() . '">' . get_the_title() .  '</a></li>';
        endwhile;
    echo '</ul>';
endif;

I tweaked your code a little bit so it’s pure PHP without opening and closing tags, but that’s just because it makes it a bit easier to see the logic of the changes I made. You can output the markup however you like.