Etymology has long been a hobby of mine so I looked up the origin of the term in the trusty online OED of Etymology:
"stern deck of a ship," c.1400, from M.Fr. poupe "stern of a ship," from It. poppa, from L. puppis "poop, stern," of uncertain origin. Poop deck attested by 1779. link
I found this word origin quite unsatisfying if not incomplete. I recalled a discussion once with my Dutch father-in-law. We were chatting about ships and he translated poop deck as something that resonated with poop deck but which I promptly forgot.
*looks up term*
The Dutch term for "poop deck" is kak dek. Now isn't that strange--the Dutch slang term for feces is kak* which seems to suggest that the "poop" in poop deck should have a more vulgar origin than let on by the OED.
* cf. the origin of the term "poppycock" 1865, probably from Du. dialect pappekak, from M.Du. pappe "soft dung" (see pap) + kak "dung," from L. cacare "to excrete." link