Fishing and the Water Egg
The Fishing Sidequest in Legend of Legaia starts mid way through the game in the town of Vidna. In the southern portion of town on the beach you'll find a man lounging next to a tackle box, the same location shown in the screen shot above. Inspect the tackle box then speak with him and he'll offer to give it to you. With this in hand, you're now able to fish!
Despite there being water every where in the game you're only actually able to fish in two different locations, a spot outside Vidna and the lake right next to Buma. Both of these locations are shown in my screen shots below.
I'm not going to go into depth about how to fish in this game or anything like that - if you'd like to learn more about fishing Gamefaqs has a few guides talking about it. What I am going to talk about is specifically the Water Egg and how to obtain it, since it's arguably the only worthwhile reward from Fishing.
You'll only be able to spend your fishing points at either the Vidna or Buma Fishing Pond. After you visit either Fishing Pond sign and begin the mini game press Triangle to bring up the menu, go down to Exchange Points to see a list of items that you can buy. Vidna and Buma both have different items that you can buy there, the Water Egg that we're after can only be purchased from the Fishing Pond at Buma.
That's all there is to it! Take the Water Egg to Zalan in Jeremi to receive the piece of Jewelry to summon Mule. At the end of the game after you conquer the Seru-Kai dungeon and defeat Songi you'll be able to pick up the Legendary Fishing Rod at Usha Research Center. Ride the elevator up after speaking into the tube and in the upper right hand corner of the first floor between the beds you'll find a tackle box. Inspect it for this fishing rod, the best one in the game.