Wordpress - How should you hook a session_start() when authoring a plugin?

There is no regular output and hence no header sent before template_redirect on the front end. If you need sessions on the back end too, use the action wp_loaded to cover both.

Example:

add_action( 'template_redirect', function() {

    $status = session_status();

    if ( PHP_SESSION_DISABLED === $status ) {
        // That's why you cannot rely on sessions!
        return;
    }

    if ( PHP_SESSION_NONE === $status ) {
        session_start();
    }

    $_SESSION[ 'foo' ] = 'bar';
});

Keep in mind that using sessions adds a whole set of very complex problems to your code, including security, scalability (load balancers), and following time consuming support issues. I don't recommend it.