The Data Loader, as far as I can tell, does not support Custom Metadata (and we've been given no indication if this will be available in the future). In fact, custom metadata isn't "real" data, and is actually documented in the Metadata API documentation. You could choose to use Ant and build the appropriate files that way, or you can follow the other instructions for simply loading this metadata.

Summer '20 Update

The Salesforce DX CLI can now import these records using the cmdt command. This is the recommended approach. The older tools are still technically viable, but should only be used if you somehow can't use Salesforce DX.

Previous answer:

In the implementation manual, the guide tells you how to import custom metadata:

Edit: The older version, included below in the original quote, has been deprecated. Please use this version instead. It also now includes a Deploy to Salesforce button to make it easier to deploy in fewer steps.

(Page 13)

Use the custom metadata loader to bulk load records to your custom metadata types from a .csv file. The custom metadata loader lets you load up to 200 records with a single call.

1. Download the tool from GitHub. Deploy the package to your org via Workbench. Note that you have to create a .zip file of the contents of the custom_md_loader directory instead of zipping up the directory itself.
2. Create a .csv file with a header that contains the custom metadata type’s field API names. Either the Label field or the Developer Name field is required. See sample.csv in your download for an example. If your org is namespaced, be sure to include the namespace prefix in your header.
3. From Setup, assign the Custom Metadata Loader permission set to the appropriate users, including yourself.
4. Select Custom Metadata Loader from the App Picker.
5. Go to the Custom Metadata Loader tab. The app prompts you to configure your Remote Site Settings if you haven’t already done so.
6. Select your .csv file and the corresponding custom metadata type.
7. Click Create custom metadata to bulk load the records from the .csv file.

It's possible to edit subscriber-controlled fields on public records of public custom metadata types via the metadata API, even if those records are included in a managed package. The main thing you need to remember is that both the type and the record will have a namespace in this case, so if they come from the same managed package, the full name of the record will be

packagens__TheType.packagens__TheRecord

Update for Summer 17:

Starting in Summer 17, you can asynchronously edit subscriber-controlled fields on public or protected records of public or protected types, so long as they're visible to your package's code (so, public or in your package or using your package's type), without needing to perform a callout, using the new Metadata package in Apex. You can also create new records of public or protected types--but note that new records are creating into the subscriber's namespace, not yours, so the only way to keep them hidden is if their type is protected and installed.