Crystal Hearts can be found in the Underground and below. There is no place where they would've been created more often in this area.
The optimal way to find them would be with Spelunker potions as this will illuminate them if it is on your screen. Spelunker potions are easy to make with bottled water, Blinkroot, Moonglow and either gold or platinum ore at a placed bottle or alchemy table.
So after using a spelunker potion just dig straight down to hell. Whenever you see a Crystal Heart just dig to it and then go back and continue down the original hole. When you get to hell, recall back to the top move approximately 100 blocks to the side (depending on your screen size and resolution) so that when you go down you won't be covering the same area and then repeat.
Digging down is more optimal than digging horizontally for 2 reasons:
- Faster to dig down than across. To dig down you will need to dig out two blocks as compared to digging across you will need to dig out 3 blocks.
- (Assuming you have a landscape monitor) You can see more at a time since the screen is wider than it is tall.
Digging diagonal is even less efficient as it requires 4 blocks to be dug out.
You can dig diagonal or sideways occasionally to utilize natural caves to help you go down and explore faster but when you get to hell you will need to go across more so as not to cover the same area again.