IT is only after about an hour of cutting dulse off the rocks and kelp it clings to that I realise the other harvesters around me are snacking on it.

"Try it," says one of my fellow pickers. "It's a good snack, keeps you going."

The sea explodes in my mouth. People often say seaweed is an acquired taste. But it seems to me this needs no acquiring, it's like a taste of the ocean itself, crunchy, salty, slightly slimy. What I'm eating is dulse, or dillisk: a seaweed that's been dined on for centuries, and which used to be a pub snack in the north-east of Scotland. But until now I have never eaten it. Before this harvest on Fife's Elie beach, I'd never seen anyone pick a frond of seaweed other than to try to pop a bladderwrack. Yet here we are harvesting it, as would once have been done on this coast centuries ago.

It feels like we are carrying out an age-old tradition, but actually this is casual work. We're filling buckets for Mara Seaweed, a growing business that aims to make seaweed, dried and milled and sold as seasoning, the next big thing in gourmet food.

Seaweed is a forgotten food on the brink of being remembered, summoned back to our consciousness and returned to our tables. The foraging revival may have made mushroom-hunting or wild garlic harvesting into trendy leisure pursuits, but, as yet, few are raking over the vegetables of the shoreline.

That is changing, however. Two years ago Research Councils UK declared seaweed one of their big ideas of the future. The Telegraph listed seaweed as a salt-replacement as one of "10 life-changing ideas under research at UK universities".

Seven out of 10 of the world's top restaurants have started using it. And next weekend, the Royal Botanic Gardens in Edinburgh will host its second Seaweed For Food And Health exhibition, run by the Seaweed Health Foundation. Craig Rose, the foundation's director, describes seaweed as "green gold".

Mara Seaweed co-founders, Fiona Houston and Xa Milne, began harvesting the plant around a decade ago when Houston's children were young. A journalist at the time, Houston wrote columns and a book, Seaweed And Eat It: A Family Foraging And Cooking Adventure, on the subject with Milne. But of all the plants she picked, it was seaweed she fell for. In a sense the story of Mara is partly about place, about the house in Elie owned by Houston's father-in-law and the seaweed-covered nearby beach where she walked her dog. It was a visiting Chinese friend, who pointed to the seaweed and asked Houston: "Why don't you eat it?"

Scotland's cold waters are rich with fine seaweeds, but we seem to have decided it is just for fertiliser, chemicals and health food capsules. The global value of cultivated seaweed is around £7 billion. Most of its value is as food, mainly consumed in China, Japan and Korea. "In the rest of the world," says Houston, "some 95% of the seaweed that gets harvested or farmed goes for food. People value it. In Scotland - where our nutrient-rich, cold North Sea Scotland waters produce high-value premium seafood - we export it around the world. It's mad."

Although Milne wasn't initially convinced that seaweed was "the next big thing", Houston began to research obsessively, going on courses. When she came back from Ireland armed with a collection of dried seaweeds and recipes, it became apparent this could work as a gourmet food additive and Milne too was converted. Others might have tried pushing seaweed's health benefits, but they were going for taste. They were keen to promote seaweed's umami, the rich savoury flavour identified by a Japanese chemist Kikunae Ikeda in 1908.

Most Scottish seaweed is harvested for non-food use, and even when it is used in cooking, the tendency has been to try and disguise its unique flavours. Now, trendy chefs from Mara-convert Paul Hollywood to Michael Smith at the Three Chimneys in Skye are homing in on the distinctive delights of dulse and kombu (kelp).

Meanwhile, there is a growing body of research documenting the health benefits. "The Japanese eat four grams of seaweed a day, and they're one of the healthiest nations in the world, with low cancer rates," says Houston. Her own diet has changed. She has stopped using salt entirely. "I know I'm going to sound like a double glazing salesman, but I have not been sick for the last three years."

It's mid-August and the lowest tide of the year, and as the water recedes a whole world appears, stratified in colour and species. Highest up the shoreline sea lettuce lurks in pools like damp salad. Closer to the sea are the wracks and the kelp with its under-growth of dulse. Houston rubs a piece of kelp on her face, saying it's good for the skin. I have cracked heels. She recommends a kelp bandage. From down on the rocks she also pulls out carrageen, a small feathery plant, which, in many parts of Scotland, used to be made into a milk pudding. "This seaweed is in old cookery books, in chapters on invalid cookery. It's full of antioxidants," says Houston.

So why don't we eat seaweed today? Partly it's because this was once "poor food", eaten in times of famine. Many of the communities that survived on it have disappeared, says Houston; the villages were emptied by two world wars. Another explanation is that "no-one had made it sexy" and that's what Houston intends doing.

Mara's harvesting manager Rory MacPhee is a sturdy, straw-hatted, weather-beaten maverick, who warns me gruffly that he doesn't want to be interviewed while he is harvesting. He has the air of a salty sea dog about him, but beneath the barnacles there is charm and warmth. MacPhee in fact gained the first seaweed harvesting licence ever granted by the Crown Estate in England and used to run a small business harvesting it on the Lizard peninsula, in Cornwall.

A former marine lawyer, he describes the sea as a "two-dimensional living organism". "I thought, 'Seaweed: there's a business there.' So I jacked the job in, rented my house out, farmed the kids out, and went and lived on the beach for six months. And all the time I was experimenting. I got a beach, got a boat, went fishing. Tough job, but someone had to do it."

Just over a year ago, he came north of the Border and announced to Houston that he had decided that the future of seaweed was in Scotland, because of the aquaculture industry. Farming, in other words, was the future. "I said why don't you just come here and join us," says Houston. "And he did." MacPhee moved up last summer, managed the wild harvesting, and lived in a caravan next to the drying operation so he could get up in the middle of the night to turn the seaweed.

Houston and MacPhee are a pair of unconventional visionaries. And while their business may appear quirky, it is a smart operation, innovative, well-marketed and driven by research. Already they have been working with Otter Ferry Sea Fish, an established aquaculture business on Loch Fyne to begin cultivating seaweeds. Recently they won innovation funding from the UK Government to work with the Scottish Association of Marine Science to hone their method. Their products sell in Harrods, Harvey Nichols and Valvona and Crolla, and they are developing a web of export connections. In March they were runners-up for a Sustainable Use of Natural Resources Award.

In other words, there's pragmatism here. Houston comes from farming stock. Her parents farmed on the west coast near Gretna, and she sees this work as her real calling after years as a journalist and political campaigner. "I'm a dispossessed youngest daughter of a farmer. Basically we're a farm with no farm, and no farm buildings."

Meanwhile, MacPhee, who is researching pre-Christian Celtic mythology and Scottish herbal medicine, prides himself on his talents for process design. It's something he learned, he says, from designing boats and furniture. "Learning how to build a chair using 83 different components is very good training for running a seaweed operation, because it's all process design."

The scene on Elie beach today is a little like that in a famous 1904 painting by William Marshall Brown, called The Dulse Gatherers. Only today, the gatherers are dressed in wet suits, and they carry plastic baskets, not wicker creels. Among them is a downhill mountain biking champion, a man who makes wooden skis, some students, a few foraging fanatics and a former BBC producer. They are here for the work, but also, I suspect, for the experience: roaming waist-deep through the tide. This is casual work with a difference. Many of them are staying all week, camped on the floor of a bothy-like cottage with only temporary electricity and a toilet that is operated using a bucket of water.

Some admit that before they came here they, like me, didn't know their dulse from their laminaria digitata (kelp). Emma Atkinson, a downhill mountain biker, says she thought "seaweed was seaweed". However Graeme Doherty remembers that he snacked on dulse, tipped off by the local fishermen when he was growing up in Dunbar. "There were people there who had worked on the sea for years and they knew these things," he says.

Tansy Torkington has been harvesting herself for the last couple of years, on the beach just south of her home in Fife, while her young children play. She now has a greenhouse for seaweed-drying, since her husband got fed up with it hanging around the house. He calls it "beachkill". But Torkington has nevertheless made seaweed an integral part of her diet, putting it in stocks and soups. She suggests I take some sugar kelp home and hang it on my washing line. "Dried, it goes really sweet," she says. "It's perfect for the children and it's full of minerals. My kids get seaweed every day, either a bit to nibble or sprinkled in food."

MacPhee says seaweed is particularly good for older women, worried about bones and osteoporosis. "Calcium pills are good but for the body to absorb calcium, you need magnesium. Seaweed has calcium and magnesium in appropriate quantities." She says iodine-rich kelp is also highly beneficial for pregnant mothers.

As the tide water advances, the tangled forest disappears beneath the surface, the rocks it clings to submerging, once more hidden. For the harvesters, most of the day's work is done. Kelp is taken away in a canoe and lugged up to the house in sturdy black binliners. Roast chicken is shared round a large wooden picnic table, served with bread, mayonnaise and liberal sprinklings of dulse. Houston scatters it on mine, but cautiously, "in case you don't like it".

In fact I am on my way to becoming a dulse addict, immediately hooked on this long-forgotten food. Fast-forward a week and it seems almost impossible to get through a meal without a small sprinkling.

My seven-year-old says it's lovely; but my five-year-old won't touch it. I have become obsessed with photographs of seaweed. Images of kelp, wafting in clear waters, or sea lettuce, floating on rock pools, make me salivate. I linger over them, hardly able to wait to get back to the beach. Next time I see weed, I will eat it.

The Seaweed For Health exhibition is at the Royal Botanical Gardens in Edinburgh on September 6 & 7. Mara seaweed is a