Searching against a WCM store is the same as searching against a full repository. However, the scope of the search will be limited to that web project only.

A search against an AVM store can be performed via Java, JavaScript, FreeMarker template, or the node browser. It is not yet exposed via open search. As the API is the same, searches via web services or something similar are the same apart from the store context.

Search is only available for the latest snapshot of the head revision for staging. It is not available for User Sandboxes, workflow sandboxes, and so on. In a lot of cases, the design principle followed is to use Lucene queries minimally in your project. Other methods such as navigating via AVM Paths and others to get hold of the content you are trying to search can suffice in such a scenario.