Here's a site I found, Cap, that offers some of the theories. The O'Neill family was from County Tyrone, and the biographies I read that mentioned this usually pointed to the Moors story:

>10) What are black Irish and shanty Irish?

--------------------------------------------------------------------------------

This question has come up fairly regularly on the newsgroup but has never been resolved definitively. Neither "black" or "shanty" are used much in Ireland. They seem to be mainly used in America.
"Shanty Irish" was used to describe the poorest of the poor Irish immigrants, the kind who ended up in shanty town (the origin of the word "shanty" is not known, but it might come from the Irish "sean tí", meaning "old house"). Today "shanty" in the States is a derogatory term for people who in Ireland might be known as culchies but the people so described need not necessarily be of Irish descent.
"Lace curtain Irish" could be as poor as the Shanty Irish but they had notions of being more respectable. They were called that because they would put up lace curtains for appearances sake, even in a shanty town. Thus the term is far from being a compliment.

{ Thanks for clarification to Neil Cosgrove. }

"Black Irish" is often taken to mean Irish people with dark hair and eyes. One romantic story is that they are the descendants of shipwrecked sailors of the Spanish Armada. Unfortunately for the story, it is very unlikely that enough of the sailors survived for their genes to be in the population visible today. A variation on this theme says they are descended from Spanish Moors who traded with people on the west coast of Ireland. Another explanation is that it's common in Irish to give people nicknames based on their hair, such as Seamus dubh and "black Irish" is just a carryover of this into English. Some people say that the "black Irish" were the original inhabitants of the island and all the rest were just blow-ins.
One other interpretation is that "black Irish" refers to the descendants of Irish slaves taken to the Caribbean island of Montserrat during Cromwell's time. The descendants of these slaves and black slaves from Africa live there to this day. The surprising thing is that they still speak with an Irish accent!<

http://www.faqs.org/faqs/cultures/irish-faq/part08/section-10.html

And here is an engrossingly detailed and thorough investigation and discussion of all aspects of the myth:

http://www.darkfiber.com/blackirish/