j and autojump
Via blaxter, I got to know autojump. It hooks into your shell, tracking the directories you visit, and provides a “j” command that allows you to cd to a directory by providing a string or regular expression that matches the directory you want to visit. To decide among various possibilities, the code has gotten to know the frequency with which you’ve visited each directory, and how long you stayed on it (or, rather, how many commands you execute in it, it seems).
I’ve been using it for a week now, and it indeed improves The Shell Experience™.
By the way, if you’d rather not execute a Python script with every prompt (!), there seems to be a small sister project/clone written in shell and awk here.