Where do Macs from before 2011 store their recovery and startup disk menu?
There really isn’t any difference between where the EFI holds the boot info from pre 2009 and post 2009 Macs
Basically, the boot manager resides in the EFI which of similar to the BIOS in a PC. It’s just the bootable part that loads the kernel is located on the drive itself.  So, you can put a blank SSD into a Mac and the boot loader will work, it just won’t find anything to load.
Now the difference in pre and post 2011 Macs (generally speaking) is if the Mac supported Internet Recovery or not. If it did, you could load an operating system (Recovery) off the Internet even with a blank SSD. If you can’t use Internet Recovery, you’ll need bootable media like a DVD or USB stick to install the OS. Once the OS is installed, you’ll her a boot partition and a Recovery partition that you’ll be able to see and select with the boot manager (by holding Option  when booting).
So bottom line, even if you have a blank SSD in your Mac, if you have a bootable volume attached (like to USB) the boot manager will find it and boot from it or display it as an option (holding Option when booting )