As far as I know, worms do spawn like any other mob, just off screen and then dig their way into the ground and towards the player (only exception to this that I know of would be Wyverns). Chance is they spawn either into underground holes (if there's any in the underworld, which I'm not entirely sure) or in obsidian structures.Well most mobs won't spawn on lava but I have my doubt on bone serpent which tends to come straight out of lava pools.
lava slimes, demons, hell bats etc.