The CRM Webservices API allows the change of the data in the record or set of records being manipulated but it can't invoke the workflow behaviour to change the workflow state.
You can have a Web Services call change the stage and the status fields and any other data field you want but the workflowstate information for that record in the workflowtables can't be touched.
Changing workflow state can actually be pretty tricky to do in the COM API too. Controlling Workflow State In ASP
But it is important to realise that all the Web Services Insert,Update and Delete actions pass through the data services layer of CRM so will potentially trigger table level scripts. This also applies for ASP and External COM calls using the Record object. CRM's Web Services and CRM's COM APIs discussed
So although you can't drive explicit workflow behaviour, implicit behaviour such as emails and further data manipulation e.g. Audit trials can happily take place.