Ubuntu – Pressing enter produces ^M instead of a newline

For example, if I am tail -fing a file or reading user input, <Enter> will produce ^M in the terminal instead of ending the read or adding a newline to stdout. ^J works fine.

I'm sshing into the ubuntu system, if that matters. This happens to me both in zsh and bash. One solution I played with is remapping the ^M to ^J in zsh, but that seems like it wouldn't fix the root problem. Anyone know what might be causing this?

Edit: To answer some questions, I'm sshing into Ubuntu from OSX. I'm using iTerm and zsh. I also forgot to mention that I'm using tmux on the Ubuntu machine.

Edit 2: Missed a question. When I type Ctrl-V Enter I get ^M (both on OSX and Ubuntu).

Edit 3: On OSX and Ubuntu echo $TERM produces screen-256color.