Recently, for my project I was trying to do the same thing, but unfortunately there was no material available in the net. The only help I got was from MSDN Sharepoint Development forum. So I thought of documenting this, so if anyone who is looking for this can be find it useful.
First of all, if you want to get data recursively, then use the following code.
System.Xml.XmlElement queryOptions = xmlDoc.CreateElement("QueryOptions");
queryOptions.InnerXml = "<ViewAttributes Scope=\"Recursive\" />";
Now for getting data from a particular folder inside a list, use the following code
string url = "http://server/sites/site/list/folder";
queryOptions.InnerXml = "<Folder>" + url + "</Folder><ViewAttributes Scope=\"Recursive\" />";
The remaining portion of accessing the webservice is already documented in the following post.