In the sense of an experienced sailor - the same as an 'old salt', someone who's been well salted by the sea - the term goes back to the 19th century, and may come from an old term for seal or from dogfish, which were also known as sea dogs. In the 16th century sea dog referred mostly to privateers.