The Collaborative International Dictionary of English v.0.48:

Sea legs \Sea" legs`\
   Legs able to maintain their possessor upright in stormy
   weather at sea, that is, ability to stand or walk steadily on
   deck when a vessel is rolling or pitching in a rough sea.
   [Sailor's Cant] --Totten.
   [1913 Webster]