My large world went into hardmode, and the underground hallow appeared in a place that I've explored. Should the underground corruption do the same, or was that just coincidence? If not, how can I find it? Just keep digging?
The easiest way to find the diagonal stripe of Corruption in your world is simply to walk along the surface, looking for an area of Corruption that you didn't notice before (this assuming that you've explored all of the surface from coast to coast). Quoting from the Hardmode wiki page:
Immediately, two diagonal stripes of the new biomes, The Hallow/Underground Hallow and Corruption/Underground Corruption (or Crimson/Underground Crimson), are generated, replacing large sections of the World in a "V" or "X" pattern that extends from the center of The Underworld all the way to the surface.
So, these stretches are guaranteed to reach the surface level of the map. Finding this new area of corruption is made even easier if you took the time to corral the existing corrupted areas with a trench before entering hardmode (something I personally like to do to prevent the existing corrupted areas from spreading).
Probably the easiest way is to load it up in a map editor such as TEdit (which I sometimes use).
Outside of that, it's nothing more than just searching around manually. It should spawn as a slightly diagonal biome, and will spawn completely at random anywhere on the map. Digging down a ways and building a long horizontal pathway is probably the easiest way.
Just remember that it will now spread like the hallow, so eventually the area will be large enough to find its way to the surface.