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.

Custom Metadata Type records are considered Metadata, and as such can't be inserted or updated directly via standard DML operations. Trying to do so will result in a TypeException with a message like:

System.TypeException: DML operation INSERT not allowed on ISVNamespace__MetadataTypeName__mdt

The Metadata namespace was added to Apex in Summer'17/v40.0 and provides the ability to deploy certain types of metadata asynchronously without having to resort the to Metadata API.

There is a good example of how this works in the Metadata Operations - Deploy Metadata documentation.

public class CreateMetadata{
  public void updateAndDeployMetadata() {
    // Setup custom metadata to be created in the subscriber org.
    Metadata.CustomMetadata customMetadata =  new Metadata.CustomMetadata();
    customMetadata.fullName = 'ISVNamespace__MetadataTypeName.MetadataRecordName';

    Metadata.CustomMetadataValue customField = new Metadata.CustomMetadataValue();
    customField.field = 'customField__c';
    customField.value = 'New value';

    customMetadata.values.add(customField);

    Metadata.DeployContainer mdContainer = new Metadata.DeployContainer();
    mdContainer.addMetadata(customMetadata);

    // Setup deploy callback, MyDeployCallback implements
    // the Metadata.DeployCallback interface (code for
    // this class not shown in this example)
    MyDeployCallback callback = new MyDeployCallback();

    // Enqueue custom metadata deployment
    Id deployRequestId = Metadata.Operations.enqueueDeployment(mdContainer, callback);
  }
}

Note that this is an asynchronous operation and you need to provide a callback Apex class that implements the Metadata.DeployCallback interface.

This would be something like:

public class MyDeployCallback implements Metadata.DeployCallback {
    public void handleResult(Metadata.DeployResult result,
                             Metadata.DeployCallbackContext context) {
        Id jobId = context.getCallbackJobId();

        
        switch on (result.status) {
            when Succeeded {
                // Deployment was successful
            }
            when SucceededPartial {
                // The deployment succeeded, but some components might not have been successfully deployed. Check Metadata.DeployResult for more details.
            }
            when Failed {
                // Deployment was not successful
            }
            when Canceled {

            }
            when Pending, InProgress, Canceling {
                // Queued or state changing
            }
        }
    }
}

The DeployResult that comes back via the callback has a number of useful properties that correspond to monitoring an API based Metadata deployment result.

Generally you should rely on the callback to monitor the deployment and then take further actions. However, if you want to be less asynchronous you can use the DeployResultId and the Toolking API to speed things along.

This can't be in the same transaction as the enqueueDeployment as it will block subsequent callouts.

This example pulls the resulting MetadataComponentId out of the successfully deployed components.

public void checkDeployStatus(Id deployRequestId) {
    HttpRequest req = new HttpRequest();
    req.setHeader('Authorization', 'Bearer ' + UserInfo.getSessionID());
    req.setHeader('Content-Type', 'application/json');

    req.setMethod('GET');     
    String instanceName = System.Url.getSalesforceBaseUrl().toExternalForm();
    // You might need to adjust instanceName if you are working from Visualforce
    req.setEndpoint(instanceName + '/services/data/v49.0/metadata/deployRequest/' + deployRequestId + '?includeDetails=true');
    
    Http http = new Http();
    try {
        HTTPResponse res = http.send(req);                 

        if(res.getStatusCode() == 200) {
            String responseBody = res.getBody(); 

            DeployResultJson jsonResult = (DeployResultJson)JSON.deserialize(responseBody, DeployResultJson.class);

            if(jsonResult.deployResult.details != null) {
                for(Metadata.DeployMessage dm : jsonResult.deployResult.details.componentSuccesses) {
                    if(dm.fileName == 'package.xml') {
                        continue;
                    }

                    Id newMetadataComponentId = dm.Id;

                }
            }
        }
    } catch(System.CalloutException e) {
        // Exception Handling
    }
}

// Support unpacking via JSON.deserialize from deployRequest metadata api call
public class DeployResultJson {       
    public String id;
    public Object validatedDeployRequestId;
    public Object deployOptions;
    public Metadata.DeployResult deployResult;
}