If you buy a fishing rod at the fishing shop (top right of map) you can fish and have a chance to obtain a sea chest. If you get a sea chest you have a chance of getting the Fish Knife (1/1500), Trident(1/3000) and Pirate Swords(1/5000). 
(Credit to Joshua for the statistics for sea chest rares) |
Um, don't credit me for this, I got this info from a guy by the name of Kaleb that I met along the beachside while I was fishing.