Lion Recovery with a Disk Wipe

I just did this yesterday, so it's still fresh in my mind. Make sure that when you restart your computer, you hold Cmd-R to enter recovery mode. Inside that, choose "Disk Utility" and there you can erase your Mac OSX partition.

If you do not do that and simply select "Reinstall Mac OS X", then it will not erase your drive, but just overwrite the parts that need to be overwritten.

Note that you will not be able to erase the Lion recovery partition this way. All options to modify this partition are disabled in Disk Utility. There is really no need to wipe this, and erasing and formatting the main partition should be sufficient.