There are two origin stories that I often heard when I used to live in Japan; the highborn story and the lowborn story.
The highborn story occurs in the early 1800’s with a samurai lord named Sakai. Sakai enjoyed fishing and whenever he caught something worthwhile, he would task his court calligrapher to document it. With a brush and sumi ink, they would write down all the details that fishermen even today wish to remember; the size, the weight, how and where it was caught. However, the story continues that there was a clever calligrapher and instead of writing down the details, he took the ink, brushed it onto the fish and then laid the paper on top to create a print. Sakai was taken by it and the practice began. There are a few surviving examples of these at the Honma Museum.
The lowborn story coincides with the moving of the capital from Kyoto to Edo (present day Tokyo). Craftsmen and construction workers from all over Japan converged to the new capital, most of whom are said to have been illiterate. So rather than writing down what was available that day to a crowd that couldn’t read, the food stalls and fishmongers would display a gyotaku print of the daily catch instead.