[Note: The information is based on what I know and have achieved using the Linux kernel v2.1.112 on a P75+ with an ATI VideoExpress 2MB graphic card. Feel free to email me with information/special cases for different graphic cards]
Assuming you are using menuconfig, you will need to do the following steps:
Go into the Code Maturity Level menu, and enable the prompt for development and/or incomplete drivers [note this may change for future kernels - when this happens, this HOWTO will be revised]
Go into the Console Drivers menu, and enable the following:
VGA Chipset Support (text only) - vgafb - used to be part of the list above, but it has been removed as it is now deprecated and no longer supported. It will be removed shortly. Use VGA Text Console instead.
Ensure that the Mac variable bpp packed pixel support is not enabled. [As of 2.1.111, this seems to get enabled if Advanced Low Level Drivers is initally selected]
Make sure these aren't going to be modules. [Not sure if it's possible to build them as modules yet - please correct me on this]
Then rebuild the kernel, modify /etc/lilo.conf to include the VGA=ASK parameter, and run lilo, this is required in order for you to be able to select the modes you wish to use.
Reboot the kernel, and as a simple test, try entering 0301 at the VGA prompt (this will give you 640x480 @ 256), and you should be able to see a cute little Penguin logo.
Once you can see that's working well, you can explore the various VESA modes (see below) and decide on the one that you like the best, and hardwire that into the "VGA=x" parameter in lilo.conf. When you have chosen the one you like the best, look up the decimal equivalent from the tables below and use the corresponding decimal number (i.e. for 1280x1024 @ 256, you just use "VGA=775"), and re-run lilo. That's all there it is to it. For further references, read the LoadLin/LILO HOWTOs.