You need to have a Late 2011 or later model to use Network Recovery. Otherwise, you need the original software restore disks that came with the computer when it was new. Models earlier than the aforementioned came with 10.6.6 or 10.6.7 which cannot be downloaded nor is available for a retail purchase. You would need to do this:
Upgrading to Lion
You can purchase Lion at the Online Apple Store. The cost is $19.99 (as it was before) plus tax. It's a download. You will get an email containing a redemption code that you then use at the Mac App Store to download Lion. Save a copy of that installer to your Downloads folder because the installer deletes itself at the end of the installation.