The climbing perch (actually not a perch, but gourami) has an organ called a labyrinth, which allows the fish to breathe air from the atmosphere for hours at a time. The labyrinth organ is full of "lamellae," which are maze-like plates of thin bone that are covered with a membrane. Oxygen passes through the membrane,where it's absorbed into the blood and distributed through the body. Good thing for the climbing perch, because they have small gills and live in oxygen-poor water, so they need an alternative way of getting air. It's not the end of the world for them when their water dries up, because, unlike most other fish, they can wander off in search of a new home. As you can see in the video, they move across the surface by pulling themselves along with their pectoral fins and gill covers. They have spines under their gill covers to help in the task, and it's said that these spines can hurt anyone unfortunate enough to be on their receiving end.
These guys are called "climbing perch" instead of "walking perch" because they supposedly have been seen in trees. However, many are skeptical and suggest that any fish in trees were taken there by birds.