Interesting that this thread should come up today. My wife and I attended today's performance of the Flamenco Society and we were enthralled. My wife is a dancer, but neither one of us has even experienced flamenco before.
The leader of the troupe said that flamenco is native only to Spain, and that it has Roma roots. It was originally a singing style - the dancing came later. The songs sung in the performance were partly Spanish, and partly Roma, which is why I had such a hard time understanding much of the singing. The leader told me that the singing and dancing were a conversation between the singer, the guitarist, and the dancer; and were improv directed by the dancer for the most part.
The leader did not know of any connection to Portuguese fado singing, but I'm guessing there must be some connection.
Ah, it was a glorious afternoon!!