Attempts to formally define steampunk are exercises in futility, similar to similar attempts at defining science fiction. Even Damon Knight's definition of SF as "what we mean when we point to it" is problematic, as the "we" no longer refers to a single cohesive group. While the Oxford English Dictionary defines steampunk as a "writer of science fiction which has a historical setting (esp. based on industrialized, nineteenth-century society) and characteristically features steam-powered, mechanized machinery rather than electronic technology; (also) such writing as a subgenre of science fiction," I believe that this definition fails to capture the extent to which it is commonly used. Steampunk is no longer merely a literary genre, as adaptations to film have been embraced as a retrofuturistic style, which has formed an almost entirely unrelated aesthetics movement. Some fellow students in my creative writing class were actually surprised when I mentioned that I was reading steampunk novels. "They have steampunk books now, too?"
When K.W. Jeter coined the term in a letter printed in the April 1987 issue of Locus, it referred to the "gonzo-historical manner" in the Victorian fantasies written by James P. Blaylock, Tim Powers, and K.W. Jeter himself. Since then, the term has been embraced and extended by numerous groups. Any particular definition will depend on which books they have read.
What is required in a steampunk novel? What characterizes steampunk? As Mike Perschon notes, The Anubis Gates by Tim Powers is in an interesting position. It is much more fantasy than science fiction. It does not really deal with technology in any significant way. It was however, included in Jeter's original term. Does this make it steampunk canon? Setting aside the technological requirements of steampunk, there are certain aspects of The Anubis Gates which are commonly reflected in other steampunk works. Power's novel is an adventure story, based primarily in Victorian London. It includes a number of contemporary literary figures, such as Samuel Taylor Coleridge, and Lord Byron. Including historical figures is a technique shared with other steampunk novels such as The Difference Engine, by William Gibson and Bruce Sterling, where characters such as John Keats play a role, as well as Cherie Priest's novel Boneshaker, which includes the Duwamish indian Princess Angeline, daughter of Chief Seattle as a character. One of the key aspects of a steampunk novel appears to be some unbalancing of power, whether it be social or political. This is commonly seen as the "punk" aspect, and Powers certainly includes it in his novel. While Powers is careful not to change historically recorded facts (his works generally fit within a subgenre known as "secret history", which include fantastic elements framed within the recorded framework of history), there are certain revolutionary aspects of his work.
What is needed to declare a work steampunk? Is steam-powered technology necessary? Jay Lake's Mainspring and Escapement novels successfully substitute clockwork machinery. Is technology itself needed? Tim Powers shows us a rule-based magic in the Anubis Gates. Is the neo-victorian era necessary? While many early steampunk books were based in Victorian London, many are now based in America, while others are based in other imaginary worlds, such as China Mieville's Bas-Lag series. What seems to be important is that the novel is set in a time of political, industrial or social change.
Steampunk may not even necessarily fall under some definitions of science fiction. Often, steampunk uses scientific theories which are no longer plausible. The use of magic in The Anubis Gates would exclude it from some people's definition of SF. The aetheric technologies of K.W. Jeter's Infernal Devices would also cause some definitions problematic. The zombie-producing Blight gas in Boneshaker is another more fantastic element.
Steampunk is generally not hard science fiction. However, Gibson and Sterling's Difference Engine eschews most fantastic elements. Their main departure from our timeline is that Babbage's Difference and Analytical Engines worked, were efficient, and formed the backbone of an early information age, leading to large social change. While it was the first steampunk novel I read, and it originally formed the core components of my personal definition of steampunk, The Difference Engine lacks the more fantastic elements which most steampunk novels now include.
Steampunk is a re-imagining of the past. This retaking of the past is inclusive, both of literary forms, and of definitions. When one moves from literature to other forms of media, the boundaries of steampunk become more nebulous. I'm a fan of the anime movie "Steamboy", and it certainly hits most of the characteristics of steampunk. Other movies, such as Will Smith's Wild Wild West, or the film adaptation of the League of Extraordinary Gentlemen certainly contain aspects of the steampunk aesthetic, but are less successful at being anything other than a dumb action movie. I think an excellent argument could be made for including Joss Wheedon's Firefly as part of steampunk.
For another look at how someone defines steampunk, see the steampunk FAQ from Cherie Priest.