Minecraft specifically is procedurally generated. The game world basically consists of a bunch of mathematical algorithms for how to generate the world based on a random input, these are part of the game code and relatively small. That random input is distilled down to a single number called the seed, and using that seed you or any one else can recreate the environment assuming they have the same algorithms (ie. a compatible version of Minecraft). Individual changes the player makes to the world are then stored in the player's save file. But beyond that, the game world can extend almost an infinite amount using the same world generation algorithms (though you might get some oddities once you reach certain practical limits, hence Minecraft enforces an artificial boundary).

Most games do not use procedural generation, their worlds are hand-crafted or at least pre-determined. Even in this case it's not necessarily a problem to store a large world. The game's data might say, this map is 100x100 "virtual metres" and brown, and at coordinate 0,0 is a 2x2x2 metre red cube. It's just a few numbers, it doesn't take much space. Similar to procedural generation, all you're really storing is instructions for how to render the world (you're storing more numbers, but the algorithms for turning the numbers into 3D objects are far less complicated).

Now change the map to be 1000x1000 "metres", and the cube to be 4x4x4 metres. The map is an order of magnitude larger, but all you've really done is change some numbers; you're still using the same amount of data to describe a much bigger world. So the size of the virtual world doesn't really correlated with the amount of data needed to describe it.

What does increase the size of the game data though is complexity. Instead of a single cube, maybe it's thousands of triangles in the shape of a house. It's no longer a solid red colour, but it has detailed wood and brick textures. And the map isn't a 1000m^(2) flat plane any more, it's a realistic terrain with hills and valleys defined by a height map, littered with trees of varying heights at different x,y coordinates. Now your game world needs far more numbers, and other data like texture images, to be stored.

Portable devices today can easily store gigabytes of data and have relatively powerful processing capability; but even so, game developers need to ensure they balance graphical detail with the hardware resources they have available.