Wordpress - Custom Post Type Plugin: Where Do I Put The Template?

So what's the best practice here?

I would say a combination of letting the theme handle it and providing a default with your plugin.

You can use the single_template filter to switch out the template. In your callback, see if the theme provided a template for the post type, if it did, do nothing.

<?php
add_filter('single_template', 'wpse96660_single_template');
function wpse96660_single_template($template)
{
    if ('your_post_type' == get_post_type(get_queried_object_id()) && !$template) {
        // if you're here, you're on a singlar page for your costum post 
        // type and WP did NOT locate a template, use your own.
        $template = dirname(__FILE__) . '/path/to/fallback/template.php';
    }
    return $template;
}

I like this method the best. Combine it with providing a sound set of "template tags" (eg. the_content, the_title) that support whatever custom data that goes along with your post type and you give the end user a lot of customization power along with some sound defaults. Bbpress does this sort of thing really well: includes user templates if it finds them and provide a lot of template tags.

Alternatively, you can use a callback with the_content filter, and just change stuff in the content itself.

<?php
add_filter('the_content', 'wpse96660_the_content');

function wpse96660_the_content($content)
{
    if (is_singular('your_post_type') && in_the_loop()) {
        // change stuff
        $content .= '<p>here we are on my custom post type</p>';
    }

    return $content;
}

You could hook into template_include and return your plugin file if the request is for your post type:

add_filter( 'template_include', 'insert_my_template' );

function insert_my_template( $template )
{
    if ( 'my_post_type' === get_post_type() )
        return dirname( __FILE__ ) . '/template.php';

    return $template;
}

But this will change the look drastically. There is still no clean solution.