I always add these two lines to ${HOME}/.inputrc (just for me) or /etc/inputrc (all users) to enable prefix-based bash history search using the Page-Up and Page-Down keys:
"\e[5~": history-search-backward
"\e[6~": history-search-forward
After editing the inputrc you have log out and in again for the changes to take effect.
Oleander Donovan's IT blog 