Creating a wordpress plugin where users can override templates

You have to write it yourself. Check out the way WP e-commerce does it:

First, the function to “register” the theme files.

function wpsc_register_theme_file( $file_name ) {
    global $wpec_theme_files;

    if ( !in_array( $file_name, (array)$wpec_theme_files ) )
        $wpec_theme_files[] = $file_name;
}

And then the function to find a theme file:

/**
 * Checks the active theme folder for the particular file, if it exists then return the active theme directory otherwise
 * return the global wpsc_theme_path
 * @access public
 *
 * @since 3.8
 * @param $file string filename
 * @return PATH to the file
 */
 function wpsc_get_template_file_path( $file="" ){

     // If we're not looking for a file, do not proceed
     if ( empty( $file ) )
         return;

     // No cache, so find one and set it
     if ( false === ( $file_path = get_transient( WPEC_TRANSIENT_THEME_PATH_PREFIX . $file ) ) ) {
         // Look for file in stylesheet
         if ( file_exists( get_stylesheet_directory() . "https://wordpress.stackexchange.com/" . $file ) ) {
             $file_path = get_stylesheet_directory() . "https://wordpress.stackexchange.com/" . $file;

         // Look for file in template
         } elseif ( file_exists( get_template_directory() . "https://wordpress.stackexchange.com/" . $file ) ) {
             $file_path = get_template_directory() . "https://wordpress.stackexchange.com/" . $file;

         // Backwards compatibility
         } else {
             // Look in old theme path
             $selected_theme_check = WPSC_OLD_THEMES_PATH . get_option( 'wpsc_selected_theme' ) . "https://wordpress.stackexchange.com/" . str_ireplace( 'wpsc-', '', $file );

             // Check the selected theme
             if ( file_exists( $selected_theme_check ) ) {
                 $file_path = $selected_theme_check;

             // Use the bundled file
             } else {
                 $file_path = WPSC_CORE_THEME_PATH . "https://wordpress.stackexchange.com/" . $file;
             }
         }
         // Save the transient and update it every 12 hours
         if ( !empty( $file_path ) )
             set_transient( WPEC_TRANSIENT_THEME_PATH_PREFIX . $file, $file_path, 60 * 60 * 12 );

     }elseif(!file_exists($file_path)){
         delete_transient(WPEC_TRANSIENT_THEME_PATH_PREFIX . $file);
         wpsc_get_template_file_path($file);
     }

     // Return filtered result
     return apply_filters( WPEC_TRANSIENT_THEME_PATH_PREFIX . $file, $file_path );
 }

In an init hook, the plugin registers all the theme files that it needs using wpsc_register_theme_file():

wpsc_register_theme_file( 'wpsc-single_product.php' );
wpsc_register_theme_file( 'wpsc-grid_view.php' );
wpsc_register_theme_file( 'wpsc-list_view.php' );
wpsc_register_theme_file( 'wpsc-products_page.php' );
wpsc_register_theme_file( 'wpsc-shopping_cart_page.php' );
wpsc_register_theme_file( 'wpsc-transaction_results.php' );
wpsc_register_theme_file( 'wpsc-user-log.php' );
wpsc_register_theme_file( 'wpsc-cart_widget.php' );
wpsc_register_theme_file( 'wpsc-featured_product.php' );
wpsc_register_theme_file( 'wpsc-category-list.php' );
wpsc_register_theme_file( 'wpsc-category_widget.php' ); 

And then when the file is actually needed, they call wpsc_get_template_file_path():

switch ( $display_type ) {
        case "grid":
            include( wpsc_get_template_file_path( 'wpsc-grid_view.php' ) );
            break; // only break if we have the function;

        case "list":
            include( wpsc_get_template_file_path( 'wpsc-list_view.php' ) );
            break; // only break if we have the file;
        default:
            include( wpsc_get_template_file_path( 'wpsc-products_page.php' ) );
            break;
    }

Obviously the code would look different for your plugin, but the principles should be the same.