I found a walking stick in act 1, on a table in the training room on the pit level (with the poisoned imp / bony monster), west of the library. A couple others were dropped randomly or offered for sale.
After blowing up the citadel, you are in act 2. Explore the island, and then rescue a couple imps from the prison when you are done. One of the imps will show you how to leave the island.
