27.12.4 Spontaneous Entry to Incremental Search

If Emacs spontaneously displays ‘I-search:’ at the bottom of the screen, it means that the terminal is sending C-s and C-q according to the poorly designed xon/xoff “flow control” protocol. You should try to prevent this by putting the terminal in a mode where it will not use flow control, or by giving it enough padding that it will never send a C-s. If that cannot be done, you must tell Emacs to expect flow control to be used, until you can get a properly designed terminal.

Information on how to do these things can be found in the file INSTALL in the Emacs distribution.