Use the DWS.asmx Web Service. It looks something like this:

server.Dws dwsService = new server.Dws();
dwsService.Credentials = System.Net.CredentialCache.DefaultCredentials;
dwsService.CreateFolder("DocumentLibraryName");

The WSS object model poster MindSharp provides has proven extremely
handy... Are there any plans to produce something like that for the
available WSS v3 web services?

I was recreated for WSS v3 in Q22006, however, I haven't had the time to
finish it so far. The goal is to get it done by Tech Ed 2007. I know,
nearly a year later than it had to be but it just hasn't been a priority
thus far.

If someone is willing to volunteer some time to vet the poster for the
RTM bits, we could start printing them sooner. Ping me directly if you'd
have some time. We would compensate you, of course.