"two authors who are each well-known and have distinctive styles in their own right" - not according to them. In fact, they make this point multiple times - in the introduction to the book and elsewhere - that they were not "the Terry Pratchett" and "the Neil Gaiman" 1 . Gaiman hadn't written any novels at that time (okay, one novel - Don't Panic, a companion to H2G2). Pratchett had only begun the Discworld cycle, and had only Colour of Magic published and The Light Fantastic about to be published.
Gaiman met Pratchett during an interview - he claims he was the first person ever to do an interview with Terry Pratchett. Some time after, Gaiman had a short story (5000 words) 2 , but he did not know how it ended. He sent it to Pratchett (among other people), and the latter said he wanted to know how it ended, so he proposed Gaiman either sells him the idea of the book, or they write it together.
They state in the introduction to the book 5 that Gaiman had more influence on the beginning of the book, while Pratchett had more influence towards the end.
They had divided the characters 2, 3 - Gaiman wrote the parts with the four Horsepersons (before they get to the air base, at which point Pratchett took over), and Pratchett wrote the parts with Agness Nutter's execution and Them (before they set for the air base, at which point Gaiman took over) - but by the end each had written some parts for each character.
They would discuss the plot on the phone, and then it would be a
mad dash to get to the next good bit before the other one could
Gaiman says in the same interview that
then we'd go footnoting each other's bits, and adding gags
Since the Internet was not a thing back then, they would exchange their drafts in the form of floppy disks.
This BBC website 4 offers an interview with Neil Gaiman, where he says mostly the same things:
Terry took the first 5,000 words and typed them into his word processor, and by the time he had finished they were the first 10,000 words. Terry had borrowed all the things about me that he thought were amusing, like my tendency back then to wear sunglasses even when it wasn't sunny, and given them, along with a vintage Bentley, to Crawleigh, who had now become Crowley. The Satanic Nurses were Satanic Nuns.
[. . .]
We wrote the first draft in about nine weeks. Nine weeks of gloriously long phone calls, in which we would read each other what we'd written, and try to make the other one laugh. We'd plot, delightedly, and then hurry off the phone, determined to get to the next good bit before the other one could. We'd rewrite each other, footnote each other's pages, sometimes even footnote each other's footnotes.
We would throw characters in, hand them off when we got stuck. We finished the book and decided we would only tell people a little about the writing process - we would tell them that Agnes Nutter was Terry's, and the Four Horsemen (and the Other Four Motorcyclists) were mine.
[. . .]
All that remained was to find a title for the book we'd written. I suggested Good Omens, Terry liked The Nice and Accurate Prophecies of Agnes Nutter, Witch. We compromised, or rather, we collaborated, and we had a title and a subtitle.
People still ask us who wrote what, and, mostly, we've forgotten. We tried to make sure that by the end we'd each written all of the major characters (I handed over the Four Horsemen to Terry when they got to the air force base, and I took the Them). There were bits we were both convinced we had written, and bits we were both convinced that we hadn't.
1 Interview excerpt on YouTube
2 Another interview on YouTube
3 A longer interview on YouTube (starts at 6:45 and goes on for ~15 minutes; also see 33:35 for a very nice story about Terry Pratchett)
4 http://www.bbc.com/news/magazine-30512620
5 Which I don't possess at the moment, and which only appears to exist in relatively recent editions.
