In order to start fishing you need to obtain a Fishing Rod. The most common way is to complete a building quest for Riah. Upon completion of her ideal fishing spot, she gives you a Fishing Rod. You can also purchase one from the Catalog.
Once you have a Fishing Rod, it's as simple as walking up to a body of water (Lakes scattered throughout the island, or the Ocean.) and clicking on the water while the Fishing Rod is equipped.
The game will prompt you to press a combination of numbers. The easier ones are simply the numbers 1-4 in sequence. More difficult to catch fish may have you press two numbers at once.
It's a fairly simple process, but can take getting used to. Keep at it and you'll be completing the Fish catalog in no time.