Our friends at Word Detective have this to say:
"While "six feet under" meaning "dead and buried" (from the standard grave depth of six feet) might seem the source of "deep six," it actually began as a nautical term. In the days before sonar, soundings of the water's depth were taken by the "leadman" with a weighted line marked in fathoms (a unit equaling six feet). A leadman's cry of "six deep" or "by the deep six" meant six fathoms (36 feet), or quite a bit of water, beneath the keel. Since something jettisoned into six fathoms of water was unlikely to ever be seen again, by the early 20th century "deep six" had come to mean "to get rid of" something, especially by putting it where it could never be found."