Heh... I'll post the same book recommendation I typed out a minute ago: "Indian Fishing" by Hilary Stewart has a lot of good info in it, from catching fish to cooking them using natural materials. I learned a lot.

I don't fish much, but back on the res we used to collect and cook shellfish at low tide, sometimes during beach picnics. It was fun. Berries, goosetongue, seaweed, and sea asparagus were also plentiful, but for some reason we didn't eat them often. I should call home to see if any recipes will work while out hiking.