There are ways to text match against encrypted documents, at least approximately, without requiring homomorphic encryption.

One simple scheme would be to encrypt in ECB mode (which has it's own disadvantages, which I'll ignore for now). Then, say that we have a relatively long string to match, we can encrypt that string with the same key (after trimming to the block size) and simply search for it's encrypted form in the document. If you see a match, and the string isn't an exact multiple of the block size, you need to decrypt a portion of the file (which you can easily do in ECB mode) and perform a more-exact match.

I wouldn't recommend this in a real system, but it's one example of how you can keep data encrypted at rest without requiring complete decryption for string matching.

I don't, on the other hand, know of any results in homomorphic encryption that would allow you to do the same thing with that approach.

It's for performing any function on the data. A search is a function which takes the data as input and returns the search results as output.

While that may be true, text search over documents has certain requirements that differ from the use cases being mentioned for homomorphic encryption over the past two years (since Craig Gentry's paper on fully homomorphic encryption). Although possible over structured data that you'd find in a database, I'm not sure if there's been a clear way to apply homomorphic encryption to search. If there has been progress made in this area, I'd love to know.

In documents, keywords are scattered through the plain text and conjunctive keyword search should be possible without giving way to dictionary attacks: If I search for 'fire truck' I want a sentence 'the truck was firing up' to potentially return as a search result, but at the same time I don't want to encrypt each tokenized word ('fire', 'truck') and pattern-match the ciphertext.

Encrypted search is an active research area. One of the more interesting/cited papers I've come across on the topic is Conjunctive, Subset, and Range Queries on Encrypted Data by Boneh and Waters [1] although there are several others. Boneh also authored an earlier paper on encrypted search involving public key encryption.

[1] http://crypto.stanford.edu/~dabo/pubs/papers/search.pdf

[2] http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf

All the homomorphic schemes I've seen do addition and/or multiplication. Is there one that does substring matching, or can you somehow use addition and multiplication to search?

I wonder if you could develop a parameterized algebra over a search string x that defined x as the identity for addition or multiplication.