Then again, this is the 21st century. I cannot imagine the food they eat would differ too much from the food you're currently eating in Seattle/Chicago/SV/London/etc.
http://seasteading.org/seastead.org/commented/paper/infra.ht...
Even if fish were sufficient, I don't think any of the inhabitants would appreciate eating fish and fish alone day in, day out. Non-perishable goods like crackers, chips, Pepsi, coffee, sugar, flour, etc. can be shipped in large quantities and cheaply (via barges). But stuff like eggs, milk, fresh meat, and other goods that can be held in storage for long periods of time without adversely affecting the quality and nutrition of their constituents need some other solution.
At any rate, they'll have an easier time at getting something to eat than the inhabitants of the International Space Station for sure :)
If they can't stomach being in somebody's exclusive economic zone (not that it makes much practical difference) then they'd have to be 200 miles offshore, making grocery runs a bit more of a pain but still possible. A reasonably fast ship will get you there and back in a day.
Also, there's lots of healthy stuff that can be kept in dry form. (Fruits, Legumes, and grains.) They will also have the ability to keep things frozen. Chest freezers can be highly efficient. Especially if they are not opened very often.
Joking aside, they could probably trade something to have someone float a few cows their way.
"Of course, one major role of government is to provide security, which would seem to be an issue on the open sea. But Friedman's not worried about defense beyond simple firearms because he thinks pirates will lack the financial incentive to attack the seasteads.
"More sophisticated pirates will take entire container ships that have tens of millions of dollars of cargo and 10 crew [members]," he said. "On a seastead, there's a much different crew-to-movable assets ratio."
In fact, his only worry is that a government will try to come calling and force their jurisdiction upon them. Toward that end, they are planning to fly a "flag of convenience" from a country that sells them, like Panama, to provide them with protection from national navies. "
Also, you should check out the website (http://www.seasteading.org) and read the FAQ. The founders have thought of the obvious questions.
http://www.spiegel.de/international/spiegel/0,1518,385048,00...