As you can only find the abyssal rune of Zot on Abyss:3 or deeper, you'll want to seek these out while exploring the hellish terrain. The deeper you go, the higher the chance of finding the rune, but the monsters you face will get progressively more numerous and dangerous.
Abyssal Stairs were added in 0.12 when the Abyss became a multi-floor branch, but they existed as a notorious practical joke in earlier versions of Crawl. Supposedly, after spending 100,000 turns in the Abyss, a portal to the Abyssal Stair could be found. While the exact contents of this realm were never quite clear, most versions of the story involved unique bosses, runes, and a secret entrance to the Realm of Zot at the very bottom. In reality, it merely made a lot of naïve players extremely bored and frustrated.