Initially on Balamb Island, on the Alcauld Plains at the foot of the Gaulg Mountains; however, in Disc 2, when the game switches to Squall's arrival at the Garden after the Missile Base event, the building becomes mobile and no longer has a fixed location.
Balamb Garden [Final Fantasy VIII Original Soundtrack: Disc 1, Track 02]
Serving as the military force SeeD's headquarters, Balamb Garden was the first of the three Gardens to come into existence, having been founded by Cid Kramer and his wife, Sorceress Edea, around twelve years prior to the start of the game. Because Cid had no funds to make all of the couple's dreams come true, he requested the financial help of NORG, a rather
f**cked-up wealthy-but-greedy member of the Shumi tribe. With his eyes set on the profit that was bound to flow in when SeeD started being requested and dispatched all over the world, NORG agreed to lend his money, therefore becoming Master of the Garden (this, however, does not give him any "real" power inside it: Cid, as the Headmaster, is still the one making the decisions). As with both subsequent Gardens, the building that became Balamb Garden was an ancient Centra shelter, used by the Centra people to move around the world after their home continent was destroyed by the Lunar Cry, about eighty years before the game's events. This is why Gardens have the ability to move, as is later revealed when Balamb successfully dodges Galbadia's missile attack by activating this device (Trabia Garden, on the other hand, never got to escape on time...).
Although Balamb Garden was founded based on Edea's idea of creating a "haven" for orphans of the Sorceress War (SeeD and Garden both got their names after "[Edea and Cid's] wish to raise the seeds of the future in their garden"), as well as train them into powerful mercenaries who could defeat the next Sorceress if needed, these goals were quickly forgotten and covered up when SeeD began offering military help around the world in exchange for money. In fact, SeeDs weren't even aware of their true duties until, upon Sorceress Edea's possession by Ultimecia, it became absolutely necessary to let them in on the secret, so that they could and would fulfill their mission.
Balamb Garden is smaller than Galbadia Garden, but bigger than Trabia Garden. It isn't as strict as the former nor as informal as the latter and, contrary to both, it allows (and relies on) the use of Guardian Forces and para-magic. Squall, Quistis, Zell and Seifer all grew up here.
Balamb Garden is the place Selphie transferred to in order to take the final SeeD admission exam, which wasn't available in Trabia; upon her arrival, she was placed in Quistis's classroom, and that is how Squall first met her: on the morning of the aforementioned exam day, when she was running late for her very first class.
Despite being a new student, Selphie had no problem becoming popular in the blink of an eye. She immediately took over Wimbly Donner's spot as the head of the Garden Festival Committee
(...are there any other members?), and even created her own website, where she actually kept a public diary and drooled over Laguna (quite the sophisticated gal, our Sefie). If not for anything else, she got to meet a lot of new people by going around asking for help with the Garden Festival and consequently, you know, annoying everybody to death. Anyway, Selphie created new bonds extremely quickly, as could be expected from her, and takes her position and duties as a SeeD very seriously – the second she became one, she began doing research on the specifics of Balamb Garden, such as the use of GFs. Also, considering for how short a time she's been around, she has a scary amount of team spirit and dedication to her new home, an instinctive attitude she probably picked up from the way she was raised in Trabia: she does insist on going all the way over to the Missile Base to stop it from being destroyed, despite knowing she is already too late to save her former Garden (revenge alone? Hardly...). In conclusion, while she may not yet be as loved in Balamb as she was in Trabia, she is certainly adapting well, and seems quite comfortable where she is.