Auto setup “permalink” or request notice

You can check if the user has left it on the default, i.e. not chosen a permalink scheme, by testing if get_option( 'permalink_structure' ) is empty.

I don’t think it’s polite to just change the user’s option for them, especially since they’ll need to update their .htaccess or equivalent before it’d actually work. Here’s a quick example to put in your theme’s admin functions to emit a warning in the header:

if ( '' == get_option( 'permalink_structure' ) ) {
    function wpse157069_permalink_warning() {
        echo '<div id="permalink_warning" class="error">';
        echo '<p>We strongly recommend adding a <a href="' . esc_url( admin_url( 'options-permalink.php' ) ) . '">permalink structure</a> to your site when using WPSE AwesomeTheme.</p>';
        echo '</div>';
    }
    add_action( 'admin_footer', 'wpse157069_permalink_warning' );
}

A more-fully-formed solution (also as a gist) with localisation and which only displays when appropriate:

if ( is_admin() && ( ! defined( 'DOING_AJAX' ) || ! DOING_AJAX ) ) {
    /* Admin-site only code */

    /**
     * If we don't have a permalink structure configured, and if the user has
     * permission to configure one, display a warning at the top of the admin
     * site. (We can't yet test which screen we're on.)
     */
    if ( ( '' == get_option( 'permalink_structure' ) ) &&
         current_user_can( 'manage_options' ) ) {
        /**
         * If we're not already on the permalink configuration page, display a
         * warning recommending the administrator configure one.
         */
        function wpse_157069_permalink_warning() {
            $screen = get_current_screen();
            if ( ! isset( $screen ) || ( 'options-permalink' != $screen->id ) ) {
                echo '<div id="permalink_warning" class="error">';
                echo '<p>' . sprintf(
                     __( 'We strongly recommend adding a %s to your site when using WPSE AwesomeTheme.' ),
                     sprintf( '<a href="https://wordpress.stackexchange.com/questions/157069/%s">%s</a>', esc_url( admin_url( 'options-permalink.php' ) ),
                         __( 'permalink structure' ) ) ) . '</p>';
                echo '</div>';
            }
        }
        add_action( 'admin_footer', 'wpse_157069_permalink_warning' );
    }
}