What distribution are you using? It may help, as some distros have graphical ways of achieving what Alloydog recommends above.
If you are using Mandrake/iva or PCLinuxOS, use the M/P Control Centre to make 1024x768 available. If not, you will have to do as alloydog says in the post above.
I found on my laptop with PCLinuxOS, although the liveCD correctly booted up at 1024x768, after installation it only worked in 800x600, but going through the control centre I was able to put this right. When you are told to "Restart X Server" close all programs and press CTRL-ALT-BACKSPACE to do this.
Asus Asus M2N32 WS Pro+Athlon AM2/4200+ â€” GeForce 7600GT â€” 2Gb Cosair VS RAM â€” 500Gb WD5000AAKS SATA Drive â€” PCLinuxOS