There is a fascinating article by Justin Sonnenburg from Stanford in the April 8 edition of Nature (Volume 464, 837-838) entitled "Genetic pot luck." I'm sorry that you need to pay to get full access, but here is the major point.
It turns out that humans are not designed to digest the kind of seaweed that is used to make sushi. However, if you eat enough of it, you ingest enough of the marine microorganisms that live on seaweed that they serve to help you digest seaweed. But it is not just colonization by these microorganisms: It comes about when the microbiota in your gut acquire genetic material from these other organisms through a process called lateral gene transfer.
With regard to the particular problem of digesting the nori used to wrap sushi,
The analysis revealed that these [genetic] sequences are abundant in the intestinal microbiomes of Japanese individuals, but not in the microbiomes of residents of the United States. The authors conclude that seaweed, which is prevalent in the Japanese diet . . . was probably the source of the microorganisms that introduced the useful genes. Although it is not clear when in human history the transfer, or transfers, of these genes occurred, continuous consumption of seaweed is the likely selective force that drove the retention of this "polymorphism" in Japanese microbiomes.
Wow. How about that!
Now, for me, this raises the reverse question. Once we have evolved to be able to metabolize seaweed, do these bugs in our gut notice when we don't eat it for some period of time and cause us to have a craving for maki? In other words, do they send a message to the brain that somehow says, "Feed me sushi?"
(Thanks to former HMS Dean Joe Martin for telling me about the article.)