To fish, use a Fishing Rod (you also need worms with you, to use as bait). After 2006 summer update you can put the fishing rod on the hotkey, so it's easier to fish.
Note: Only shallow water contains fish! Also each water square has one fish which needs to respawn after it is caught, which takes approximately 30 minutes.
<spoiler>
Can be found at daily spawns in the fishing hut near Thais, in Nargor kitchen, Edron orcs, in a house in Sabrehaven and many more places in Tibia.
