Walling is the act of intentionally narrowing the passageway between strategical points by placing buildings in a certain setup. The most common examples are Terran Wall-Ins and Protoss Fast Expansions, but Zerg also have put Evolution Chambers and Sunken Colonies in combination to good use.
A single squared area in StarCraft, or one matrix, is a 32 pixel wide, 32 pixel high area. All buildings in StarCraft have a span of at least 2x2 matrices areas (64x64 pixels). However, even though the buildings appear to fully occupy the area as you are choosing where to build them, the vast majority do not. They have gaps. These gaps are extremely annoying to deal with for new players trying to wall-in; experienced players learned to deal with it through continual trial and error. Once these gaps are accurately measured however, it's possible to predict whether a certain wall-off combination will block a specific unit or not before even trying them.
It's not so easy however, since map-specific doodads, cliffs, and neutral buildings also have their own gap values. Without knowing them, we cannot accurately predict what buildings can block what in each choke, on each map, only between the buildings we know the values of. There is yet to be a comprehensive list of all the cliffs, doodads, and neutral buildings' gaps.
By looking at the List of Unit and Building Sizes we can see how big of a gap is left when placing two buildings together. We can then search the List of Unit sizes and see what units fit through that gap.
In a Protoss vs. Terran's early game, Terrans usually create walls at their ramps to prevent any Protoss unit from entering their base. This keeps the Protoss from scouting the Terran as well as keeping him safe while he techs. Terran wall-ins are usually created with Supply Depots and Barracks, though Factories, Bunkers and other buildings are used sometimes too.
On some maps, like Luna it's not possible to create wall-ins at the ramp because of the presence of unbuildable terrain near it. On this type of map, Terrans opt to create gaps with their buildings that Marines can walk by, but Zealots can't. The following is an example of this, known as creating a Sim-City:
In the picture above, the gap left between the Command Center and the Barracks has 21 width. Marines are 17 and Zealots 23. As a result if a marine is kept in the middle of the building formation it will not be reachable by zealots. By doing this the Terran player can micro the marine in and out of the gap while firing at the Zealot. However, later on during the game, it might be necessary to have Comsats ready in case of impending pushes, so you might need to lift the barracks and build somewhere else.
It is important to see the order in which we position our buildings too.
The wall-in on the right has a gap of 25 pixels between the Barracks and the Supply Depot. This will let Marines through, as well as Zealots and SCVs. The one on the left is a much tighter formation. The biggest gap is 15 pixels tall, which will keep even Zerglings out, but as a con Marines will spawn outside of our base and Barracks will need to be lifted to let them in.
If you place 2 buildings cornered, the gap is the same as if they were one by each other as you can see in this picture:
Other buildings can be used to wall in. For example we could use a factory as shown in the picture to create a Zealot-tight wall-in and lift our Barracks to scout our opponent.
Gaps can be used offensively as well. A popular strategy used in Protoss vs. Zerg in the map Ride of Valkyries involved proxying two Gateways below the opponents ramp so it left only a small gap between them. This would allow the Protoss player to block the gap easily with his first zealot to keep the Zerg in his base, while he could produce more zealots. Nal_rA used this strategy vs Mondragon during Blizzcon 2005 on a different map, Nightlight. 
Boxer showcased an offensive wall-in vs. JulyZerg in the map 815. Boxer proxied two barracks near July and attacked his expansion. He built a third Barracks blocking the path that lead to July's main, stopping the reinforcements and throwing him off-balance.