Emacs ido-style shell
Since I also wanted something like this, I tried to implement it as a bash completion function. Obviously it means. you have to use bash.
It is only lightly tested, so please feel free to try and report bugs /comments.
http://pgas.freeshell.org/shell/bash-ido
Bash has an environment variable called CDPATH which can contain a list of directories to search when using the cd command. Also, check out the "Programmable Completion" and "READLINE" sections of the Bash manual. You should be able to cobble together something that works for you.
Try the Z-shell. It has much better completion than bash. I must admit I haven't used it for a while though and stuck with bash because it's always available.