This is the guide to replacing the hard drive in your model mx6124http://support.gateway.com/s/Mobile/Q106/Blade/8511418.pdf
The directions refer you to the missing users manual, but as long as a replacement drive is recognized by the bios, your recovery cd should use it.
But that brings up a double check moment.
I don't have a gateway bios handy to check with but there are usually a couple of places where the hard drive is detected and its model and or serial number displayed in the setup screens.
I see above that you checked the boot order, but that sometimes can be misleading since it does not name the actual device by model number, only referrers to it by generic term.
Look for ide or ata settings or something similar. Older models had a auto detect you had to trigger but I think this one should have list that looks like :
And should identify your cdrom/dvd by name as one of the lower three. Some laptops only have primary master and slave.
If the bios can see and id the drive, then look closely at the detected geometry. Load setup defaults and try the recovery cd again.
Check with your friends. Lots of people have old laptop hard drives you could use for testing. I have a stack of 3 to 8 gb I keep for the purpose.
You local computer store might also have an adapter like the one in this pic:http://www.laptoprepair101.com/laptop/2006...sktop-computer/
Should be less than 10.00.
Which would let you put the drive on the secondary master of a desktop and see if it can be seen by the os.
This would let you run scandisk, check for virus/malware and back up any files you might want.
However, if the drive can be seen in a desktop, and a replacement or test drive cannot, you might be looking at a mainboard replacement and unless you really want to learn all about the innards of a laptop and comeup with some cash to boot, it may not be worthwhile.
Gateway points you to the missing manual to see what size drive you can use with the bios. It comes with a 60 so it should take that for sure. It should also take an 80 or a 120 since those were available as options.