I have C!ed the annoyingly thorough geeklizzard for stealing my thunder. I did not imagine anyone would have noded the Vauxhall Gardens yet. All I can do is add some contemporary descriptions, and give some notes on the name.

There are two possible origins for the name. One is straightforwardly from the name of an early proprietor, Jane Vaux, around 1615. This theory is advanced in a remarkably accurate book on etymology I have, so I view this idea with respect. It however says "in 1615", not making it clear whether that means some sort of pleasure establishment was founded there on that date.

The alternative origin is that Vauxhall and Fox Hall are alterations of Falkes Hall, said to be from Falkes de Breauté, who was lord of the manor there in the time of King John, for whom he was captain of mercenaries. This theory is stated in The Oxford Companion to English Literature and repeated in a footnote to John Evelyn's Fumifugium (which calls it Fox Hall).

In neither case is it clear whether the gardens were named after a suburb or district already called Vauxhall, derived from some other hall there, or whether the gardens came first and the district took on their name. My guess is that the Falkes theory is correct and the modification to Vaux is by chance association with a later holder, Jane Vaux.

Curiously, the name has been borrowed into Russian as the word for 'railway station': vokzál (pronounced vag-ZAL); first citation being as foksal in a St Petersburg newspaper of 1777. It also occurs in Polish as wokzał and wogzał.

There has been a millennium bid to try to create a new sort of pleasure garden at Vauxhall. In a reply to the House of Commons, the Secretary of State for the Environment, Sir Paul Beresford, said "I look forward to seeing those plans. I am intrigued, as an Edwardian historian has given me a description of the pleasure gardens which raises some rather interesting smirks and question marks."

Here are two descriptions of Vauxhall, both from Humphrey Clinker by Tobias Smollett, published in 1771.

I no sooner entered, than I was dazzled and confounded with the variety of beauties that rushed all at once upon my eye. Image to yourself, my dear Letty, a spacious garden, part laid out in delightful walks, bounded with high hedges and trees, and paved with gravel; part exhibiting a wonderful assemblage of the most picturesque and striking objects, pavilions, lodges, groves, grottoes, lawns, temples, and cascades; porticoes, colonades, and rotundos; adorned with pillars, statues, and painting: the whole illuminated with an infinite number of lamps, disposed in different figures of suns, stars, and constellations; the place crowded with the gayest company, ranging through those blissful shades, or supping in different lodges on cold collations, enlivened with mirth, freedom, and good-humour, and animated by an excellent band of musick. Among the vocal performers I had the happiness to hear the celebrated Mrs. -----, whose voice was so loud and so shrill, that it made my head ake through excess of pleasure.
and from a different character a different perspective:
The diversions of the times are not ill suited to the genius of this incongruous monster, called the public. Give it noise, confusion, glare, and glitter; it has no idea of elegance and propriety--. . . Vauxhall is a composition of baubles, overcharged with paltry ornaments, ill conceived, and poorly executed; without any unity of design, or propriety of disposition. It is an unnatural assembly of objects, fantastically illuminated in broken masses; seemingly contrived to dazzle the eyes and divert the imagination of the vulgar--Here a wooden lion, there a stone statue; in one place, a range of things like coffee-house boxes, covered a-top; in another, a parcel of ale-house benches; in a third, a puppet-shew representation of a tin cascade; in a fourth, a gloomy cave of a circular form, like a sepulchral vault half lighted; in a fifth, a scanty slip of grass-plat, that would not afford pasture sufficient for an ass’s colt. The walks, which nature seems to have intended for solitude, shade, and silence, are filled with crowds of noisy people, sucking up the nocturnal rheums of an aguish climate; and through these gay scenes, a few lamps glimmer like so many farthing candles.

When I see a number of well-dressed people, of both sexes, sitting on the covered benches, exposed to the eyes of the mob; and, which is worse, to the cold, raw, night-air, devouring sliced beef, and swilling port, and punch, and cyder, I can’t help compassionating their temerity, while I despise their want of taste and decorum; but, when they course along those damp and gloomy walks, or crowd together upon the wet gravel, without any other cover than the cope of Heaven, listening to a song, which one half of them cannot possibly hear, how can I help supposing they are actually possessed by a spirit, more absurd and pernicious than any thing we meet with in the precincts of Bedlam?