If you are on Exchange Service 2007 or higher you can easily create folders using the Exchange Web Services (EWS). EWS are a set of SOAP services exposed by Exchange Service making it fairly easy to do a number of different tasks on Exchange programmatically.
The easiest way to call EWS is through the Exchange Web Service Managed API which is a .NET wrapper for calling EWS from a .NET client.
When using EWS through the managed API you start by connecting to your Exchange Server. The endpoint of EWS is usually located at the address "/EWS/exchange.asmx" as show below:
var service = new ExchangeService(ExchangeVersion.Exchange2010_SP1);
service.Url = new Uri("https://server/EWS/exchange.asmx");
service.Credentials = new NetworkCredential("username", "password", "domain");
You might also use autodiscovery to connect to the server.
After having successfully connected, you can create a public folder in the following way (see also MSDN):
var folder = new Folder(service);
folder.DisplayName = "New Folder";
folder.Save(WellKnownFolderName.PublicFoldersRoot);
I know you tagged your question as VB.NET but please forgive my C# code examples.