Hooray! brunerd has written an easy to use utility that will create a Lion or Mountain Lion Recovery partition if you don’t have one (for example, if you performed a full-system Time Machine restore to a brand new drive). It will also update the Recovery partition to the current version of OS X, which doesn’t always happen during a standard OS X software update. It’s a little intimidating looking because he’s got the whole script on his page, but it’s quite easy to use even if you’re not a Terminal type of person — find his link to the .zip file in the post, unzip, double-click, and follow the prompts.
The utility requires that you have the “Install (Mac) OS X (Mountain) Lion” app that you purchase from the Mac App Store (it can be redownloaded if you don’t have it on your computer). You also need the free Lion Recovery Update 1.0 (even if you have Mountain Lion). brunerd’s tool is actually a meta-utility, in that it builds a new utility using pieces of the Apple downloads, which you then run to create or update the recovery partition.
If you don’t have the OS X installer because your Mac came with the version you want to install, you’ll need to buy the installer from the Mac App Store (which will also mean an upgrade to Mountain Lion if you’re on Lion), or, if you’re tech-savvy, you can perform an internet recovery (start up holding option-command-R) to install OS X to an external drive, unplug that drive as soon as it reboots during the install process, and then after reboot reconnect it and find the DMG file in its “Mac OS X Install Data” folder, and modify brunerd’s utility script to accept the DMG rather than the Install Mac OS X app. However, that may only get you whatever version of OS X came with your computer, not the latest. And that would of course all take a while, but if you keep the DMG file, you wouldn’t have to go through it again and you’d have an OS X installer at the ready if you restore it to an USB stick (as shown here starting from step 4).