The identification of prior art forms part of the Patentability (also referred to as Novelty) search type, which is probably the most frequently exercised patent search type. These searches form an essential part of the process of determining the patentability of a specific invention. In order for an invention to be viable for patenting, no prior record of a similar or identical product or process may exist. This search task aims at clarifying whether any such records exists in patent and non-patent literature that have been published prior to the filing of a patent application in question. Prior art also plays a vital role in Validity (Invalidity) searches that are exercised in order to render specific claims of a patent, or the complete patent itself invalid by identifying matter published before the filing date of the patent in question. It is of note that for this kind of searches the legally active part of the targeted patent, the claims, form the basis of the information need.
Prior art searches are the most common types of patent searches. They are performed at various stages of the patent life-cycle and with different intentions.

• Before filing a patent application. This is also called ”novelty search” or “patentability search” and it aims at determining whether the invention fulfills the requirements (novelty, inventive step) of obtaining a patent. The documents found by this search should be cited in the patent application in case the inventor decides to file one (for an USPTO application these documents should be mentioned in the ”invention disclosure form of the US Patent Offce”).
• A novelty search is carried out by the European Patent Offce before a patent is granted in order to determine a patent’s novelty and inventive step. The results of this search are fed into the EESR (Extended European Search Report). At the USPTO, the prior art found by the US patent examiner is mentioned on the front page of the document and marked with an asterisk.
• A ”validity search” (or “invalidity search”) is used to unveil prior art that invalidates a patent’s claims of originality after that patent has been granted. The results of such a search may be used to start an opposition procedure against a granted patent.
• In order to learn more about a specific field of invention.

Note that legal texts of the European Patent Office use the term “state of the art” in place of “prior art”.

How to do a prior art search ?

In our test collection a topic will be a patent document. This is what a patent examiner gets as input for conducting a prior art search. When using the test collection for measuring the effectiveness of a patent search engine, one crucial issue is how to convert the given patent document into a query. A patent examiner has several techniques for doing this. Since queries are usually keyword-based, these techniques aim at extracting a set of keywords from the given document or from a periphrasis, summary, or reformulation thereof.
By gaining some more insight on how IP search professionals conduct prior art searches, one can devise optimal strategies for automatically converting topics into queries.
The “Guidelines for Examination in the EPO”, especially “Part B: Guidelines for search” is a good starting point for learning techniques for prior art searches. This documentation is available on the EPO site at http://www.epo.org/patents/law/legal-texts/guidelines.html .
Here is a quote from section 2.1 “Subject of the search; restrictions” from Chap. IV:

Having determined the subject of the invention as outlined in IV, 1.1, it may be desirable for the examiner to prepare first a search statement, defining the subject of his search as precisely as possible. In many instances one or more of the claims may themselves serve this purpose, but they may have to be generalised in order to cover all aspects and embodiments of the invention.

Some more practical hints on how to conduct a search are given in section 2.2 "Formulating a search strategy":

Next the examiner should start the search process by formulating a search strategy, i.e. a plan consisting of a series of search statements expressing the subject of the search, resulting in sections of the documentation to be consulted for the search. In its initial phase,
a search strategy will contain one or more combinations of the basic components mentioned in III, 2.2.
The search process should be interactive and iterative in the sense that the examiner should reformulate his initial search statement(s) according to the usefulness of the information retrieved [...]

The USPTO captures the queries issued by their examiners to find prior art during the application process. This data might be useful for investigating methods adopted by patent examiners for query re-formulation. Here we describe how to access this data. 

A further informative source is D. Hund, L. Nguyen and M. Rodgers "Patent Searching Tools & Techniques", John Wiley 2007, especially Chapter 3, “The mechanics of searching”.

http://www.intellogist.com/wiki/Category:Best_Practices is a Wiki on the prior art searching process.