Some more freebie fishing advice: Dig any dirt for soil and the chance of worms, or walk around in a swamp to have leeches attach themselves to you (you'll have to detach them from your characters equipment screen) If you haven't made a hook yet: find a rabbit or chicken, and either catch or punch it. The easiest way to catch these critters is to walk all the way up to them and use the punch skill to one shot them. Once butchered, they will give you a bone which you can fashion into a hook.
It's also possible to create lures, which substitute for your worms, leeches or intestine bait. The downside to these lures is that they take longer to catch the fish, and they have the potential to break, losing your lure, hook, and/or string. Some (slightly spotty) information on fishing and what you can catch can be found at
http://ringofbrodgar.com/wiki/FishBest of luck!