A play on heterosexual, the term was first used in 1994 by British journalist Mark Simpson, who coined Metrosexual (and its noun, metrosexuality) to refer to the urban, fashion-conscious target audience of men's magazines:

The promotion of metrosexuality was left to the men's style press, magazines such as The Face, GQ, Esquire, Arena and FHM, the new media which took off in the Eighties and is still growing (GQ gains 10,000 new readers every month). They filled their magazines with images of narcissistic young men sporting fashionable clothes and accessories. And they persuaded other young men to study them with a mixture of envy and desire.
Some people said unkind things. American GQ, for example, was popularly dubbed "Gay Quarterly". Little wonder that all these magazines — with the possible exception of The Face - address their metrosexual readership as if none of them were homosexual or even bisexual.

In the summer of 2003, as most of Canada legalized gay marriage, the US Supreme Court struck down anti-sodomy statutes as unconstitutional, and Bravo introduced a cable show in which stereotypically Fabulous gay urbanites make over a hopeless, hapless hetero, Metrosexual sprang back into the public discourse after a decade of UK obscurity. Spurred on by a 2002 Salon article (also by Simpson) that "outed" metro soccer megastar David Beckham and a new study by marketing firm Euro RCSG Worldwide, Metrosexuality got a memetic steroid injection in the form of a New York Times Sunday feature (front page, Arts and Leisure) and trickled into local news outlets from sea to shining sea.

Simpson's take is detached, wittily ironic, with more than a dash of anticorporate disdain --

The typical metrosexual is a young man with money to spend, living in or within easy reach of a metropolis -- because that's where all the best shops, clubs, gyms and hairdressers are. He might be officially gay, straight or bisexual, but this is utterly immaterial because he has clearly taken himself as his own love object and pleasure as his sexual preference. Particular professions, such as modeling, waiting tables, media, pop music and, nowadays, sport, seem to attract them but, truth be told, like male vanity products and herpes, they're pretty much everywhere.
For some time now, old-fashioned (re)productive, repressed, unmoisturized heterosexuality has been given the pink slip by consumer capitalism. The stoic, self-denying, modest straight male didn't shop enough (his role was to earn money for his wife to spend), and so he had to be replaced by a new kind of man, one less certain of his identity and much more interested in his image -- that's to say, one who was much more interested in being looked at (because that's the only way you can be certain you actually exist). A man, in other words, who is an advertiser's walking wet dream.
-- and includes a Sex and the City definition for females, and touches on the Queer angle only in passing --
Gay men did, after all, provide the early prototype for metrosexuality. Decidedly single, definitely urban, dreadfully uncertain of their identity (hence the emphasis on pride and the susceptibility to the latest label) and socially emasculated, gay men had pioneered the business of accessorizing masculinity in the '70s with the clone look enthusiastically taken up by the mainstream in the form of the Village People. Difficult to believe, I know, but only one of them was gay and 99 percent of their fans were straight.

-- but outside Britain, in its soundbite diffusion through the popular media, metrosexual has congealed into something more digestible: a heterosexual male who color coordinates and listens to Kylie Minogue and goes to independent movies and cares deeply about exfoliation. A straight guy who acts gay.

Addendum. U.S. presidental candidate Howard Dean declared himself a metrosexual yesterday (October 28, 2003) at a Boulder fundraiser, then backtracked several hours later, saying "I've heard the term, but I don't know what it means."

I also contributed a version of this to Wikipedia