Can you use the LIKE operator in SOQL queries via the REST API?

Yes you can. SOQL in the rest API supports all the same constructs that its SOAP older brother does. Remember to pass the SOQL as the 'q' parameter in the URL,and to URLEncode the soql when putting it in the query, e.g.

https://na1.salesforce.com/services/data/v25.0/query?q=select+id+from+account

I think the issue is with the url encoding of the % in the like clause.

I just tried the following in the Workbench Rest API and it worked.

/services/data/v25.0/query?q=select+id+from+account+where+BillingState+like+'VIC%25'