Relics start spawning randomly once you pass depth 100, and you can find them all the way down to the magma zone. Their spawn chance gets a little higher the deeper you go.
This relics update took a bit of time since I'd just gotten back from a break, and there was a lot of pixel art to draw for it (the giant Encased Relic, broken relic, and also the little relics). I'm really glad you're enjoying it :)