How can I install an SSD on my new Lion MBP w/out install disks?
The recovery partition on your original disk was the only supported method until the Recovery Disk Assistant was made available.



The bulk of this answer was written before the official steps were published - so I would recommend the Recovery Disk Assistant even though HT4718 steps help understand what is happening under the hood.

http://support.apple.com/kb/HT4718

The easiest is to get a drive enclosure or adapter and re-run the Lion installer from the Recovery HD and install Lion onto the new SSD.

It likely won't matter if the drive with the recovery HD is on an external bus or an internal bus, but I would keep the original drive inside the mac until you have Lion installed on your SSD connected to an external port.

Boot off the SSD to test it and run migration from the internal drive to the SSD before doing swapping the drives inside your mac.

It still boggles my mind that any mac will ship without some sort of reinstall media. Look in the center of the box, under where the mac sat. Call apple if your media is missing so they can ship it to you or point out how they want you to reinstall the OS on a new drive. Your mac's hard drive is listed as a consumer replaceable part, so they have to provide you with the steps to do that.