How to provide translations for a WordPress TinyMCE plugin?

Use the filter 'mce_external_languages'. From wp-includes/class-wp-editor.php:

The following filter loads external language files for TinyMCE plugins.
It takes an associative array ‘plugin_name’ => ‘path’, where path is the
include path to the file. The language file should follow the same format as
/tinymce/langs/wp-langs.php and should define a variable $strings that
holds all translated strings.
When this filter is not used, the function will try to load {mce_locale}.js.
If that is not found, en.js will be tried next.

$mce_external_languages = apply_filters('mce_external_languages', array());

I would just use a copy of wp-includes/js/tinymce/langs/wp-langs.php … and drop that superfluous mce_escape() in favour of the original esc_js().

Sample file:

<?php # -*- coding: utf-8 -*-

$strings="tinyMCE.addI18n(
    {" . _WP_Editors::$mce_locale . '.extrastrings:
        {
            helloworld: "' . esc_js( __( 'Hello World', 'my_plugin_text_domain' ) ) . '",
            foobar: "' . esc_js( __( 'Foo Bar', 'my_plugin_text_domain' ) ) . '"
        }
    }
)';

In your plugin you just use:

add_filter( 'mce_external_languages', 'wpse_44785_add_tinymce_lang', 10, 1 );

function wpse_44785_add_tinymce_lang( $arr )
{
    $arr[] = 'full_path_to_lang_file.php';
    return $arr;
}

To access the new strings in JavaScript use for example:

title : ed.getLang('extrastrings.helloworld')