Where does all void fish come from? From the Void obviously. You can get here by Void Fishing up "The Null" and defeating it will give you a Null Cell which you can craft a Void Token to teleport into the void.
By going too close to the bottom bedrock layer during a bloodmoon, the bedrock becomes unstable and noclips you into the Void Dimension (Not the empty void)
You can alternatively craft a void token early-game by crafting Dark Essence from True Black.
You can also get here by a small chance when sleeping in the overworld and experiencing a "Nightmare Event".
