A proxy building is a building built outside your own base including your natural base, generally in the proximity of your opponent's base. Despite the similarity between the words 'proximity' and 'proxy', the term actually stems from the word 'proxy' as something which in acts on behalf of someone or something else. Proxy structures do not necessarily need to be in closer proximity to the opponent, any structure built outside one's base is a proxy structure. 'Proxy' can be used either as an adjective (proxy barracks), a verb (the player will proxy four barracks), or a noun (the player's proxy in the opponent's natural).
There are two main reasons why proxies are useful. First, proxies allow your attacking units to be built closer to the enemy, which will cut down on rush time and allow you to reinforce your army more quickly. Second, if placed correctly, proxies are unlikely to be scouted by the enemy, and this may give the player the element of surprise.
Other reasons to proxy a building include: scouting, keeping an important building safe from a main base attack, or simply confusing your opponent.
Proxy Pylons are extremely common in any Protoss push that occurs after Warpgate tech. The ability to warp in groups of gateway units directly into the battle is extremely useful, and is essential for builds like the ubiquitous 4 gate. Proxy pylons can also augment an attack: for instance, building pylons along a retreat path will allow you to reinforce your army while getting farther away from the enemy's sources of reinforcement, and turn a losing battle into a more favorable outcome. Proxy pylons from different attack paths would also allow for better flanking, or for forcing the enemy to respond to engagements on multiple fronts.
Against Terran, pylons may be used in the place of Observers along the edges of the map to spot for incoming drops. Although vision is limited to where a pylon can be placed, pylons do not cost gas and do not take up supply.
Other buildings can be proxied. Against Terran and Protoss, a proxy Stargate will allow players to quickly send in an Oracle or two to harass the mineral line, to often devastating results if the proxy is unscouted. Proxy Tempest and Void Ray is less common and appears later in the game, but is still occasionally seen. A player can also hide a proxy Twilight Council in a place where it is unlikely to be found by enemy scouts, precluding a surprise Blink Strategy, or placing a Dark Shrine at the same proxy to allow for Dark Templar play.
Since many Terran buildings can fly, many Terran proxies can be recovered if map control is lost, allowing for more standard play once the proxy has either failed or served its purpose. The most common Terran proxy is the Double Proxy Barracks, used against Zerg and sometimes against Protoss, where two hidden Barracks quickly produce Marines to punish a player who opted for an economical build such as Hatchery First.
Later proxies are more risky, but can put the Terran player in a huge economic lead if the other player does not scout or otherwise anticipate them. A proxy Factory placed either close to the enemy base or floated into an unoccupied part of the enemy main can be used to quickly deliver Widow Mines to the mineral line, where they can do substantial damage until some form of detection is made. A Starport and attached Tech Lab, if not found by an enemy, can also deliver cloaked Banshees which can devastate worker lines in the time it takes for a player to detect and repel the Banshees.
Zerg proxies are the least common. Because all Zerg production happens at the same building, only the Proxy Hatch is a useful Zerg proxy. However, a player can block expansions by first building a Hatchery, cancelling it, and then using the small residual patch of creep to build another building, such as an Evolution Chamber. The high HP of the building means that a player who was attempting to expand early will need to spend both time and resources clearing away the building, at a relatively low cost of 175 minerals to the Zerg player.
Against another Zerg, a player can also bring a Drone along to make into a Spine Crawler. Once made, it can be rooted anywhere on the enemy creep and defended with the player's own Zerglings and other drones. It makes an early pool rush far more difficult to repel, and generally will force the defending player to get a Spine Crawler of his own to defend key structures and the mineral line.
Hidden tech is more common for Zerg after Lair tech has been achieved, enabling the Generate Creep ability for Overlords. Since a Zerg player can quickly use all of his available Larva to make units that to a scouting player would only appear as Eggs, a hidden tech building such as a Spire means that a large mass of units will be available to the Zerg player with very little warning to an unsuspecting enemy.