How do I make my plugin load before the headers are output so I can redirect wordpress?

The correct hook to use is template_redirect which allows you to have the necessary info available to do checks while also early enough to actually redirect. As per the example on the codex page:

function my_page_template_redirect()
    {
    if( is_page( 'goodies' ) && ! is_user_logged_in() )
    {
        wp_redirect( home_url( '/signup/' ) );
        exit();
    }
}
add_action( 'template_redirect', 'my_page_template_redirect' );

Codex page here – template_redirect