Is my HMAC secure if I have a complete series of HMAC'd prefix strings Let's say I have a long sentence, like "The quick brown fox jumped over the lazy dog." Let's further say that I need to keep this string encrypted, so I use an HMAC. Let's further further say I want to be able to do prefix searches for this string, so I also store all possible prefixes of this string, for example:

$\operatorname{HMAC}_K(\text{"T"})$, $\operatorname{HMAC}_K(\text{"Th"})$, $\operatorname{HMAC}_K(\text{"The"})$, $\operatorname{HMAC}_K(\text{"The "})$, etc. where $K$ is the key.

I recognize there are some weaknesses between rows here involving overlap, but what I'm interested in is whether having this one row's set of HMAC values is enough to make things insecure. Could an adversary work out the key, or any part of the plaintext, given a series of HMAC values for all of a given input's prefix values?

Feel free to use any flavor of HMAC if it'll help you argue that there's a weakness.
I'll start by assuming that your instance of HMAC is a secure MAC function, which comes down to making various assumptions about the hash function it is instantiated with.

If this assumption holds, then an adversary will not be practically able to recover the key, even if they have access to a large number of MACs and the corresponding plaintexts, or even if they get to choose their own plaintexts &mdash; if it was possible for them to obtain the key, they'd be able to compute their own MACs and thus commit existential forgery, contradicting the assumed security property.

As for plaintext recovery, in general there's nothing that prevents a MAC function which is secure against existential forgery from leaking some information about the input plaintext, and indeed it's not hard to delibrately construct examples of such MACs (as Ricky Demer's answer shows).

However, the security proof of HMAC given by Bellare actually proves a stronger property, namely that HMAC is a PRF as long as the compression function of the hash it is instantiated with is also a PRF (or, more generally, than HMAC is a privacy preserving MAC (PP-MAC) as defined by Bellare, as long as the compression function is also a PP-MAC and the hash function itself is computationally almost universal (cAU); see remark on Lemma 4.2).  This is a rather strong security property, and it indeed shows that, as long as the hash function satisfies the assumptions of the proof, HMAC will not leak information about the plaintext to an adversary who does not possess the key.