Can't work out Arduino 12v Relay (5v Logic)
You should connect it just like you did it.  

Common ground between the Arduino and the relay board. 

The datasheet even mentions supplying the 12V to the relay board from the Arduino 12V Vin - and that would require the ground for the relay board to be connected to the Arduino ground.

The digital IOs from the Arduino are 5V logic level.  The relay board doesn't need 5V power, it only needs 12V for the relays.  The 5V logic signals are used to drive a transistor to switch the relays.



Correction:

A closer look at the pictures (since the datasheet doesn't include a schematic) shows that the relay board uses optocouplers to drive the relay.

The board still only has one ground connection, though, so you must still connect the relay board ground and the 12V ground together.

The optoisolation doesn't really do much for you since the grounds still have to be connected.

There are apparently several versions of the board, some with and some without optoisolators.

In any case, they all share the same pinout, so you must connect the relay power ground and the Arduino ground together.