To acquire the Art of Abysswalking, you need to defeat the Great Grey Wolf Sif, who is located in the Darkroot Garden. You can buy the Astoria seal from the Undead Parish blacksmith to unlock the large sealed door guarding the area. Alternatively, you can go around the back, and follow the shoreline that harbors the Hydra (Near the giants, and the Havel tower). Sif is located just past the Forest Hunter covenant.
It is a good idea to bring a shield to this fight; With enough endurance, all of Sif's sword attacks can be blocked. The generally accepted strategy for defeating Sif, is to stay under his stomach, and strike when you are safe from his sword attacks. Like most bosses, you just need learn the patterns, and the rest will come with practice.