What is a stealth address? Stealth addresses are mentioned in the context of privacy of bitcoin transactions. What are they and how would they work?

Can they provide 100% anonymity?
As I understand it, the "stealth address" is intended to address a very specific problem.  If you wish to solicit payments from the public, say by posting a donation address on your website, then everyone can see on the block chain that all those payments went to you, and perhaps try to track how you spend them.  

With a stealth address, you ask payers to generate a unique address in such a way that you (using some additional data which is attached to the transaction) can deduce the corresponding private key.  So although you publish a single "stealth address" on your website, the block chain sees all your incoming payments as going to separate addresses and has no way to correlate them.  (Of course, any individual payer knows their payment went to you, and can trace how you spend it, but they don't learn anything about other people's payments to you.)

But you can get the same effect another way: just give each payer a unique address.  Rather than posting a single public donation address on your website, have a button that generates a new unique address and saves the private key, or selects the next address from a long list of pre-generated addresses (whose private keys you hold somewhere safe).  Just as before, the payments all go to separate addresses and there is no way to correlate them, nor for one payer to see that other payments went to you.

So the only difference with stealth addresses is essentially to move the chore of producing a unique address from the server to the client.  Indeed, in some ways stealth addresses may be worse, since very few people use them, and if you are known to be one of them, it will be easier to connect stealth transactions with you.

It doesn't provide "100% anonymity".  The fundamental anonymity weakness of Bitcoin remains - that everyone can follow the chain of payments, and if you know something about one transaction or the parties to it, you can deduce something about where those coins came from or where they went.