Hi,
EDIT: Sorry, just re-read your last post. Are you sure you've got a SYSTEM restore CD, and not a SOFTWARE restore CD? They are two very different things.
OK, just to clarify, you want to completely remove all data from your system, then stick in the restore CD to get it back to it's original state, right? If this is the case, all you need to do is format your hard drive. Restart your computer in MS-DOS mode. Once you're at a c:\ prompt, type in the following:
format c: \s
Press Y to confirm when prompted.
When the format finishes, stick your Restore CD into the drive, and restart your computer. The restore should begin, (if it doesn't, you'll have to go into SETUP, and set the system to boot from CD).
I'd like to point something out though. I've never used a Gateway restore CD, but I've used both DELL and Compaq. Both of these Restore CD's automatically format your Hard drive prior to the install, so unless Gateway is different (doubtful), you can probably just stick the CD into the drive, and reboot.