You really should properly install OS X Lion from the installer, as restoring from Time Machine backup doesn't give you the recovery partition, which will e.g. prevent you from using "Locate my Mac" and its computer locking functionality in iCloud, and from using File Vault 2.
OS X Lion can be installed onto a blank system, and you can delete previous partitions (if you have them) during installation.
Included with the App Store download of OS X Lion is a disk image you can burn to DVD and boot from. Unfortunately, it is deleted after installing Lion and you cannot redownload, as it is already installed on your computer.
You can always get that file from a friend. Depending on your country, it might be legal to download from Internet file sharing networks — you already bought and downloaded the same bits when you got Lion via the App Store. Make sure the MD5 checksum of the image file is
b5d3753c62bfb69866e94dca9336a44a — you can open Terminal, type
md5sum, followed by a space, and then drag the
InstallESD.img file onto your Terminal window and press
Enter. This will take a while.
Alternatively, you can buy a bootable USB thumb drive from Apple, or first install and set up Snow Leopard, download and configure App Store (via Software Update…), and download Lion again free of charge. Then, create the bootable DVD from the downloaded data as described on the linked web page. Afterwards, you can boot from that and install Lion cleanly, or simply update.
During installation, you are prompted whether to restore data from another Mac, or a Time Machine backup. If you now choose Time Machine, you get both the recovery partition a pure Time Machine restore would not restore, and all your data (if you want it).