How can I add a new value to a picklist using APEX?

The way to do this is using the Apex MetaData API wrapper as provided by esteemed SFSE colleague Andrew Fawcett here

1. Running user needs to have Customize Application privilege so you really want this to be an admin type user
2. Read the examples in the GIT package carefully - there is one for picklists. You need to read the CustomField from the MetaData API first then update, otherwise you'll smash all the existing picklist entries.

The relevant example in the package's MetadataServiceExamples.cls file is here:

public static void updatePicklist()
{
    MetadataService.MetadataPort service = createService();             

    // Read Custom Field
    MetadataService.CustomField customField = 
        (MetadataService.CustomField) service.readMetadata('CustomField', 
            new String[] { 'Lead.picklist__c' }).getRecords()[0];       

    // Add pick list values
    metadataservice.PicklistValue two = new metadataservice.PicklistValue();
    two.fullName= 'second';
    two.default_x=false;
    metadataservice.PicklistValue three = new metadataservice.PicklistValue();
    three.fullName= 'third';
    three.default_x=false;
    customField.picklist.picklistValues.add(two);
    customField.picklist.picklistValues.add(three);     

    // Update Custom Field
    handleSaveResults(
        service.updateMetadata(
            new MetadataService.Metadata[] { customField })[0]);        
}

@cropredy answer is correct. But there are some changes in MetadataService class. So code given in above answer will not work. Below code will work with latest version of mdapi GitHub repo.

MetadataService.MetadataPort service = createService(); 

MetadataService.CustomField picklistField =(List<MetadataService.CustomField>) service.readMetadata('CustomField', 'Lead.picklist__c').getRecords();

metadataservice.CustomValue two = new metadataservice.CustomValue();
two.fullName= 'second';
two.default_x=false;  

picklistField.valueSet.valueSetDefinition.value.add(two);

MetadataService.SaveResult result = service.updateMetadata( new MetadataService.Metadata[] { picklistField })[0];

In place of PicklistValue we have to use ValueSet. Also we need to make little change in MetadataService Class. We have to replace ValueSet virtual class in Metadatservice with

public class ValueSet {
        public String controllingField;
        public Boolean restricted;
        public MetadataService.ValueSetValuesDefinition valueSetDefinition;
        public String valueSetName;
        public MetadataService.ValueSettings[] valueSettings;
        private String[] controllingField_type_info = new String[]{'controllingField',SOAP_M_URI,null,'0','1','false'};
        private String[] restricted_type_info = new String[]{'restricted',SOAP_M_URI,null,'0','1','false'};
        private String[] valueSetDefinition_type_info = new String[]{'valueSetDefinition',SOAP_M_URI,null,'0','1','false'};
        private String[] valueSetName_type_info = new String[]{'valueSetName',SOAP_M_URI,null,'0','1','false'};
        private String[] valueSettings_type_info = new String[]{'valueSettings',SOAP_M_URI,null,'0','-1','false'};
        private String[] apex_schema_type_info = new String[]{SOAP_M_URI,'true','false'};
        private String[] field_order_type_info = new String[]{'controllingField','restricted','valueSetDefinition','valueSetName','valueSettings'};
    }