All Macs older macs provided install discs, so you have lost them. Recent models that come without a dvd-rom drive provided a USB thumb drive. Now that Lion is released, i'm not exactly sure if you get any discs or a USB thumb drive, but they will have the ability to re-install the OS from either a restore partition or from the network.
One tip with the Genius bar, go utilize one of their display models and make your appointment. If the store isn't busy, you can probably get in within an hour... It's sad that Apple's employees don't seem to make the appointment for you. The Apple Store is like Starbucks or the Soup Nazi's kitchen, you gotta learn their ways to get what you want.
As for the fresh install, take the Snow Leopard install disk boot up and start the disk utility.. You can format the drive there, reboot and you should be able to install from that point. If you have the family pack version of Snow Leopard you should be home free, i've never bought the single license but I believe it might ask you for your original install disks that came with your mac (that you lost).
