http://msdn.microsoft.com/en-us/library/ms464040.aspx
Except the fact, the article on MSDN wants you to create the WSDL and DISCO file for yourself, which I found out to be very hectic and time consuming. Instead we can just use any tool that will generate the WSDL and DISCO file for us.
1. As First Step, Create a class library in Visual Studio

2. Add the references to the “Microsoft.Sharepoint.dll” and “System.Web.Services” dll

3. Add a new class and inherit it from “Webservice” class

4. Sign the assembly. As it will be deployed in GAC

5. Write your code for the custom webserivce. Here are just two methods for renaming the folder in a document library

6. Build your project and install it in GAC.

7. Create a custom SPFolderWS.asmx file which will point to the SPFolderWS.cs (which you defined in the class library, and is installed in GAC). Note this file “SPFolderWS.asmx” doesn’t need to be in the project.

8. Use the SPDev Tool to generate the DISCO and WSDL file for you. ( You can download the SPDev Tool from the following website)
http://www.crsw.com/spdev/Wiki%20Pages/GenWS.aspx

9. Here are your generated WSDL and DISCO file.

10. Copy these files to the “C:\Program Files\Common Files\Microsoft Shared\Web Server Extensions\12\ISAPI” directory

11. Browse the URL to make sure the webservice is properly deployed

12. That’s it.
Now to test the above webservice, we will create a console application.
1. Create a Console Application, and add the reference to the webservice as shown below

2. Write the following code snippet to call the methods of the custom webservice.

3. If everything works fine, the folder should be re-named.

4. That’s All
You can also download this code from the following location.
Custom WebService Code