How do I fetch all the folders in Salesforce using REST API

You could use a SOQL query on Folder. Something like:

SELECT Id, Name, DeveloperName, AccessType FROM Folder where Type = 'Document'

Which would be a GET request to (change na5 to match your instance):

https://na5.salesforce.com/services/data/v33.0/query/?q=SELECT%20Id%2C%20Name%2C%20DeveloperName%2C%20AccessType%20FROM%20Folder%20where%20Type%20%3D%20%27Document%27

The JSON response will be something like:

{
    "totalSize": 15,
    "done": true,
    "records": [
        {
            "attributes": {
                "type": "Folder",
                "url": "/services/data/v33.0/sobjects/Folder/00l700000000001AAA"
            },
            "Id": "00l70000000wp7KAAQ",
            "Name": "Test",
            "DeveloperName": "Test",
            "AccessType": "Public"
        }, //...
    ]
}