Implementing a fast 'split' function on a stream of characters in Java
There are more-sophisticated algorithms you can use, depending on the input and the search string. Even keeping the "one character at a time" interface though, there are optimizations to the implementation. Someone linked to KMP in a comment to your question - that's a good way to go if you can do some initial setup and buffer an arbitrary amount of the incoming stream.

I think you're on the right track with a state machine, but the implementation in addChar2 looks kind of heavyweight, with the MutableInteger class and a linked list, and an iterator-driven loop, and all. If you want this to be fast, you'll likely want to use primitive types (ints and arrays of ints) rather than OO wrappers around the primitive types.