How do I know if I have the Lion recovery partition set up?
In the Terminal (located at /Applications/Utilities/Terminal.app) type:

diskutil list


You know that you have a Recovery Partition installed if you see this entry:

Apple_Boot Recovery HD             650.0 MB