With fish 2.0, the shell stores a list of "cd" commands issued from a specific directory, so mostly just typing "cd" yields an auto-completion hint out of the box.