Neil Gaiman made his name writing the Sandman series for Vertigo comics through most of the '90s. That series followed the adventures of Morpheus, the god of dreams, and wove together a wide variety of myths and legends to create a really fascinating setting for some innovative-yet-archetypal storytelling. Gaiman continued along the same lines with his novels, and he really broke through with this, his fifth, which dominated the major sf awards (and helped start the trend of fantasy's dominance in the '00s).
Gaiman usually comes off as the quintessential Brit in his writing, but he moved to the US (actually to my current neck of the woods) before this novel. Perhaps as a result, American Gods actually feels a lot like good Stephen King to me. Gaiman's works are usually about normal people thrust into magical worlds and given a destiny (In King's works, the people are a bit more blue collar, and they're less likely to get a destiny and more likely just to be trying to survive). In American Gods, the central character is a Minnesotan named Shadow, who begins the novel in prison. His wife dies, leading to a slightly early release, and Shadow ends up employed as the bodyguard of a strange man named Wednesday. From Wednesday, Shadow learns that gods are real, but they are created by human beliefs - America is overcrowded with gods because of its immigrant past, and the gods from the Norse, Greek, Hindu, and Egyptian pantheons (among others) must compete with modern technology for their survival. Shadow has all sorts of surreal encounters with these beings (both friend and foe) and most of them are extremely interesting. There are also a few very nice twists along the way (the best twists are the sort that make you exclaim "of course!" but that you still never see coming - the identity of the central villain here fits that description perfectly).
Gaiman does dodge Christianity for the most part, which seems odd considering the book's conceit and the nature of faith in the United States. I don't particularly blame him for dodging that can of worms, but it could have added another layer to the novel.
So, it's a fun novel, and just enough of a departure from his previous work to explain (and, I'd say, to warrant) his sudden wide recognition and mainstream success. Neverwhere is my personal favorite, but I'd still recommend American Gods first, especially to a fellow American. Great stuff, and a worthy winner from the fantasy side of the tracks.