So in my quest to do a clean install of OS X Lion, I deleted the recovery partition. I managed to install Windows 7 (Enterprise .iso from my uni), but I am having a lot of trouble figuring out a way to get OS X back on.
The recommended path from Apple is to upgrade from the previous version. If you don't want to do that for some reason you have to get one of these: OSX Lion USB Thumb Drive. You can also get the .dmg from the Lion install and copy that to any USB drive but this requires access to the Snow Leopard App Store.
You can read a bit about it on this blog