UseC-Q C-J
(control-Q control-J) each time you want to include a carriage return. e.g. to double-space everything
M-x replace-string RET C-Q C-J RET C-Q C-J C-Q C-J RET
Or to put "bloogie " at the beginning of every line
M-x replace-string RET C-Q C-J RET C-Q C-J b l o o g i e SPACE RET