Couple of additions to Steven's informative answer, at a technical / processing level... speaking here in a general sense of the techniques used to generate large worlds (not Terraria specifically).

**Generating the initial space**

Firstly, there are fast block copies (`memcpy` in C) that occur to allocate the initial memory (2D array) representing the world. The entire initial world can consist of zeroes, or `struct`ures all of whose members are set to zero. This could represent either your sky or your ground. Let's assume the whole maps start as sky, so then zeroes represent empty space. This is a very fast allocation. If the entire 20M tile map uses 4 bytes per tile, that is 80Mb - large, yes - but not ridiculously so by any modern measure. Even double that is modest. You are looking at milliseconds or less to allocate such a large space to main memory (RAM).

Terrain can be rapidly written & read in a couple of ways. 
 * `memcpy`, or series of `memcpy`s on a 2D array. This is not particularly efficient; see below.
 * your whole world may be represented as [RLE](https://en.wikipedia.org/wiki/Run-length_encoding) columns, running from top to bottom. This makes writes potentially even faster, since an entire column of 2400 high can be represented as nothing but a min value (2 bytes), max value (2 bytes), and the voxel type (typically 1 byte) = 5 bytes total. If you have earth (basic stone) and sky in the same column, that's 2 such entries = 10 bytes. For the whole map then, before you have started making elaborate details, that's 10 bytes * 8400 = 84000 bytes, or about 84kb. That's _nothing_, and it fits CPU L1 cache on pretty much all devices, making access super fast. Now let's imagine you have at least 50 elaborations per column, then that 50 * 84kb = +- 4Mb. Still very small.

Data access speeds improve enormously when a dataset becomes small enough to fit into CPU L1 & L2 cache, as in RLE, rather than our RAM-sized (80Mb) 2D array representation.

**Generating detail**

We could read from our RLE-encoded world map and copy small areas into small 2D arrays (for example 100x100) to create a pyramid, a small dungeon, a village etc. Once work is done, we copy these back into the RLE structure using an optimal function we've built for that purpose. What this means is that 99%+ of the entire world space is ignored as we elaborate in _just that small area_. As the world is gradually generated, we probably touch less than 20% of the entire world space.