According to Charles Funk, in A Hog on Ice:

Red herring is nothing more than herring that has been cured by smoke, a process that changes the color of the flesh to a reddish hue. The herring is intended to be eaten after such curing, but dog trainers learned long ago that red herring had a peculiarly persistent odor and was very useful, if trailed over the ground, for training a dog to follow a scent.