Add the following to your ~/.inputrc:

"\e[5~": history-search-backward
"\e[6~": history-search-forward

And of course, in order to use your ~/.inputrc you need to set your INPUTRC environment variable in ~/.bash_profile:

export INPUTRC=$HOME/.inputrc

The next time you login you will be able to run "gvim <pageup>" and the last entry that started with "gvim " will appear, <pageup> again will bring the next one up, and so on.

Note that escape codes for PageUp and PageDown vary depending on your terminal type; check out this tip for a technique on how to find out what your terminal expects.