I've been loving mcfly[0], a history search that can be bound to <ctrl+r>. It makes suggestions based on your current directory as well as your command history.

[0] https://github.com/cantino/mcfly