The RecordType object has a picklistValues property that you can use to make values available to a record type.
Once you've added your picklist value, you can retrieve the record type, update the picklistValues property with the values that should be available, and then make another update call to save the metadata.
Edit:
So to actually do this is a little more complex.
First you have to get the possible values for the field. This is necessary because updating the record type values requires the full list of available values. There's no way to append.
I've just used the Account 'Industry' field for my example. You'd swap in your object and field;
// Get the values for the picklist
MetadataService.CustomField picklistField = (MetadataService.CustomField) service.readMetadata(
'CustomField', new String[] { 'Account.Industry' }
).getRecords()[0];
After that you need to get the picklist values from the field and add your new value to the list.
MetadataService.PickListValue[] pickVals = picklistField.picklist.picklistValues;
MetadataService.PickListValue newPickVal = new MetadataService.PickListValue();
newPickVal.fullName = 'New Picklist Value';
pickVals.add(newPickVal);
To add your value to ALL record types you'd need to get your record type names somehow. Since you're using Apex you can just use SOQL or a describe call if you want. There's documentation on both so I'm not going to cover it here.
After you get you list of record types, you need to retrieve them.
String[] recordTypeNames; // get your list of record types either through a query or a describe call and put them into a list
// Get the record type from the API
MetadataService.Metadata[] mdRecordTypes = service.readMetadata(
'RecordType', recordTypeNames
).getRecords();
MetadataService.RecordType[] recordTypes = (MetadataService.RecordType[]) mdRecordTypes;
Next, initialize the RecordTypePicklistValue object that you're going to use to specify the picklist values for each record type. Then create a new RecordTypePicklistValue for the field you're adding to.
// initialize the list of record type picklist values
MetadataService.RecordTypePicklistValue[] rtPickValues = new MetadataService.RecordTypePicklistValue[]{};
MetadataService.RecordTypePicklistValue rtPickValue = new MetadataService.RecordTypePicklistValue();
// Create the recordtypepicklist and add it to the list of picklist fields for the record type
rtPickValue.picklist = 'Industry';
rtPickValue.values = pickVals;
rtPickValues.add(rtPickValue)
Finally, got through all RecordTypes and set the picklistValues to the values you just created and make an update call.
// loop through the record types and set the picklist values
for(MetadataService.RecordType RT : recordTypes){
RT.PicklistValues = rtPickValues;
}
// Update the record type
service.updateMetadata(
new MetadataService.Metadata[] { mdRecordTypes });
There are a lot of code samples in the apex-mdapi repo that can show you additional samples if you need them.