How do I input a newline character in isearch or query-replace?

Use C-q C-j. For more information, see Special Input for Incremental Search in The GNU Emacs Manual.