I know this is a pretty old question, but in case someone else finds it, this is how I've done it:
String CAML = "<?xml version=\"1.0\" encoding=\"utf-8\"?>" +
"<soap:Envelope xmlns:xsi=\"http://www.w3.org/2001/XMLSchema-instance\" " +
"xmlns:xsd=\"http://www.w3.org/2001/XMLSchema\" " +
"xmlns:soap=\"http://schemas.xmlsoap.org/soap/envelope/\">" +
"<soap:Body>" +
"<CreateFolder " + "xmlns=\"http://schemas.microsoft.com/sharepoint/soap/dws/\">"+
"<url>" + ParentFolder+'/'+NewFolderName+ "</url>"+
"</CreateFolder>"+
"</soap:Body>" +
"</soap:Envelope>";
String uri = "http://[your site]/_vti_bin/dws.asmx";
WebClient client = new WebClient();
client.Headers["SOAPAction"] = "http://schemas.microsoft.com/sharepoint/soap/dws/CreateFolder";
client.Headers["content-type"] = "text/xml; charset=utf-8";
client.Encoding = Encoding.UTF8;
client.UploadStringCompleted += UploadStringCompleted;
try
{
client.UploadStringAsync(new Uri(uri, UriKind.Absolute), "POST", CAML);
}
catch (Exception ex)
{
MessageBox.Show("Error in upload string async: " + ex.Message);
}
I was using silverlight, which is why I used upload string async, but this can be done other ways with the same http post method