I used to use z, but I've since switched to fasd. It's much like z, but also so much better. In addition to being able to do "z <part of directory>" you can do "f <part of file>". So, for example, if I've got a rails project I've worked on a lot recently I know its config.ru is high on frecency, so I'll just do "vim `f config`" to edit that file. If I want a file that's not so recent I can always do "vim `f -i config`" to pick from a list of files.
fasd is leaps and bounds above z in functionality, and I've thoroughly enjoyed using it.
I put z and fasd through their paces, and out of the box z works very intuitively. I like it. fasd takes a little more to get used to, but I'm going to put it through a full try out. Let's see if the additional features make it worth the while. In either case, thanks all for a great thread.
I don't know autojump, but from a cursory look: z is written in pure shell, is a single file, no external dependencies. autojump requires python, thus likely has more features.
IMHO, just for jumping around directories, z is good enough.