First of all you have to actually get the fishing rod. Talk to Joe and give him an egg every day. It won't take long until you're friends. Go to Maple Lake. There will be a small sequence and you'll get the rod from Joe. Now you can fish!
Fishing may be slightly confusing at first. When you first get your rod you'll get a small tutorial on how to use it. To use the rod, press the 'square' button. Move where you want to cast and then hold down the 'X' button. Once the line is cast you can let go of 'X' - you don't have to hold it the whole time. Four arrows will appear once you get a bite. These arrows will move one at a time. If the 'up' arrow moves, than press 'up' on your control pad. If the 'down' arrow moves, press 'down' on your control pad. I think you get the message here. While you're doing this, you must also hold down the 'x' button to reel the line in. After you catch the fish you can either sell it or use it for recipes.
Places/Times to Fish:
Early morning: Good
On Rainy Days:
Early morning: Best