Which bootloader do you use?
If you use lilo, then when you see the lilo screen, move the selection bar around, then go back and select your Linux entry (but don't hit return yet). Then hit the spacebar and type in vga=whatever, and you'll notice the kernel command line changing at the bottom of the screen. Hit return when you're done.
If you use grub, then you select your Linux entry, and hit some magic key that I don't remember (perhaps 'e'?). This will bring up the entire kernel command line for you to edit. Move to the end and do the same thing as with lilo -- hit space, and then type in vga=whatever. Then hit return.