You need a fishing rod to catch a fish. To craft a fishing rod, grab some sticks and some string. Open the "Tools" tab of the inventory and you'll be able to craft it.
To obtain string, you have to kill spiders. You'll usually need to kill four or five spiders to get enough string, but if you get lucky it could only take one.
After you have obtained a fishing rod, head to some water. Use your rod and a fishing bobber will fly out. Wait until this bobber sinks under water, then use the rod again to pull it in. A fish should come flying towards you. Pick it up.
Now, take this raw fish to the furnace and cook it. When it's done, you'll have a cooked fish and an achievement.