I'm certainly no expert say take this with a grain of salt...
When would you choose mechanical, versus solid state?
The big difference is the "switching time", cost, and reliability. A mechanical relay takes considerably longer to switch on and off, is general less expensive, but wears out considerably faster. For certain applications (like pulse-width modulation) a relay won't work. But, if you want simple on/off control a relay is a good choice.
From a debugging perspective, relays that have an audible "click" are nice. You can listen for the click to know if everything is working up-to and including the relay. An SSR with a status-LED is almost as good but I prefer the "click" so my eyes can be focused on other things (like a monitor).
Would I be correct in assuming that SSRs have opto-isolators built in, and as such don't need additional isolation?
I don't think it's a requirement. If you want / need the isolation you definately want to make certain the SSR includes it.
If using an SSR, where are people getting them?
From Opto 22. But I don't use them with Arduino. I get them for my "day job".