There's more than a couple of ways to do it probably. Here are a couple:
1) Use the Lion Recovery Disk Assistant and create a bootable usb flash drive.
Use that flash drive to re-install. It will require a network connection to Apple and it will download all of the most recent Lion. It will take a while depending on how much bandwidth you have. I did this at home with a decent cable broadband connection and it took me about 35 minutes for the download part.
2) Download all of the Lion installer first to a flash drive ( or DVD I guess ) and reinstall from that.
You still have to download everything ( once ) but then you have a full local copy for next time.
Info on how to do this is here ...
macworld hints