QUOTE(Elliot Cannon @ Aug 31 2012, 05:22 PM)

If so should it be between the battery and the relay? Or between the relay and the lights?
Battery to relay.
The reason to use a relay in the first place is the fact that the relay trigger current is very low.
You'd run that off one of the existing fuses anyways.
So you want to fuse the 12V supply from the battery to the relay/lights.