I'm a big fan of Gaiman and have pretty much everything he ever wrote, barring some comics and children's books, including a few rarer/limited items, several signed.
I think whether you'll like him depends on the kind of stuff you like. He's unquestionably a great writer, but he tends to have a sort of almost fairytale quality to a lot of what he writes. This can take a darker/harsher turn, as with American Gods, or a little bit of a lighter one, as with something like Stardust, or The Ocean at the End of the Lane. Either way, it's either something you like, something you tolerate because you otherwise like his style and creativity, or something you're really not into. He's not what you'd call a fantasy author, and he's more literary than what you generally think of when it comes to genre fiction, but the stuff he writes does tend to have a sort of urban fantasy vibe.
Good Omens, which he co-wrote with Terry Pratchett, is one of the funniest books I've ever read. His short story books are great too (Fragile Things, Smoke and Mirrors). Coraline and The Graveyard Book are also excellent, but technically written more for kids (and thus probably not where you'd want to start ... though they're not at all unpleasant reads for an adult).
American Gods or Good Omens are probably where I'd suggest starting, despite being very different books. Some suggest Neverwhere, but that's a bit more of a grown-up Alice in Wonderland sort of thing, bit more on the fantasy end. If you're into short stories, any of his short story books are probably fine places to start with too.
