Do I perhaps have to connect the SCL/SDA output of the sensor to my SCL/SDA pin on my Arduino?
If you have an Uno, you have connected it correctly.
Load and run the I2cScanner program to check communications and verify the device address.
It is possible that you will need pullup resistors on the I2C lines. Post a link to the exact HMC5883 module that you have.