Wipe and reinstall on Macbook Air?

How do I go about completely wiping and reinstalling Lion on my 2011 macbook air.

It didn't come with any installation media.

I just tried the CMD+R thing but its kept all my files and settings - I want to completely wipe and have it fresh.

Thanks.

Are you selling it on or something?

If you can download Lion from the App store (even if you have previously purchased it) you can copy the installer to a USB drive and do a fresh install

How to Burn Your Own OS X Lion Install DVD or USB Drive

No, I just wish to to have a fresh install so I don't have to go through and delete everything manually.

EDIT: When I goto the App Store, it just says Installed, how do I download it again?

Can I simply delete the partition and use the recovery thing?

Well I've taken the plunge and deleted the partition and going to try the recovery thing again

Just incase anyone wanted to know - IT WORKED!

-Boot into Lion recovery via CMD+R
-Use Disk Utility to erase the hard drive
-Reinsall Lion via the recovery option.