The solution is basically to set the PAGER environment variable to the program that supports color.
There are at least 5 you can choose from:
To get "most" on Ubuntu, do the following:
prompt%> sudo apt-get install most
prompt%> sudo update-alternatives --config pager