For a nautical theme, I typically either turn the pen in the shape of a belaying pin http://www.penturners.org/forum/showthread.php?t=22326, or add a decorative knot (which sailors call "fancywork") http://www.penturners.org/forum/showthread.php?t=24596. Teak is always a good choice, but other woods are used in shipbuilding as well. Cherry, holly, lignum vitae, and even purpleheart are popular. I still have a piece of angelique left over from the construction of the Spirit of South Carolina that's destined to become a "nautical" pen.
Thanks a ton everyone! I've waded through some of the suggestions...Some really cool stuff out there! I'll have to compile a good presentation and lay it all out!