I was going to replace my HDD with a SSD - but I need to install Lion for my SSD.
Do I need to install Leopard on the SSD first, then go to the Mac App Store to update?
No, you can install Lion directly if you want. This will save you a lot of time, as you would otherwise have to upgrade from Leopard to Snow Leopard first, only to upgrade to Lion afterwards.
Buy a bootable OS X Lion USB stick
You can buy a bootable OS X Lion USB Thumb Drive from the Apple Store: http://store.apple.com/us/product/MD256Z/A
Create a bootable OS X Lion USB stick or DVD based on the Mac App Store download
You cannot update from Leopard to Lion. So your options are: