Wired serial connection between two Arduinos - do they need a common Ground (GND)?
Short answer: Yes.

Rx/Tx is referenced with a logic ground. Without ground being common, there is no way to determine what is high or low.

(Sorry I don't have a more technical explanation)

Edit: I thought I would add, if you are using the same power source, then they probably have a common ground. In this case, a common power source doesn't mean the wall side of a wall adapter, but the SAME wall adapter.