The sea sponge is scientifically classified as an animal, therefore maybe it would be considered unkosher, as seafood. On the other hand, it seems much more similar to a vegetable of some kind, so would be kosher to eat.
So, are sponges kosher?
The Yerushalmi (Shabbos 7:2) mentions sponges (ספוג) in a group of items where cutting them causes them to grow back even more, and therefore declares that someone who does so has performed two categories of work, "reaping" and "planting." These melachos refer to plants, not animals, so I would think that indicates that the sponge is viewed as a plant (probably because it doesn't move around).
That said, I haven't found this Yerushalmi cited as halachah.
Another possible data point, though, might be that in the course of explaining when a sponge may or may not be used on Shabbos, Shulchan Aruch (Orach Chaim 320:18) cites Aruch, who explains that the sponge sits atop the head of a large fish (a whale, maybe?) and covers its eyes when it sticks its head out of the water, so that it doesn't see ships and wreck them. Mishnah Berurah there (320:45) alternately describes a sponge as "a wool-like material found on beaches." Both of these descriptions suggest that they saw sponges as inanimate or vegetable matter rather than an independent life-form.
Although this does not answer the question, I came across the following quote from R. Yosef Albo, Sefer ha-Ikkarim 3:1:
Coral is intermediate between inanimate matter and plants. We also find the sea sponge, which only has the sense of touch, and is an intermediate between plant and animal stages. We also find the monkey to be intermediate between animals and man.
This idea is repeated, for example by R. Moshe Isserles (the Rema) in his commentary מחיר יין, on מגילת אסתר, א:ו, and is ultimately based on Aristotle's classifications.
Assuming the key halachik distinction is that which underlies the difference between tolesh and netilas neshama in hilchos shabbos, as seems plausible, that should depend on whether sponges display some form of sentience (at least basic percepts of pain and/or pleasure, as distinct from the automated motions of machines and plants) . To some degree, modern "science" is somewhat unreliable in this analysis since contemporary scientists' materialistic dogmas interfere with their ability to classify sentience, or even to clearly ascribe it to humans, let alone lower lifeforms. Still, it does seem plausible that some form of centralized nervous system or even a brain should be necessary to say something is alive (חי) in the classical sense (or some comparable system that would mediate some low level of sentient perception). Though according to the Ri Albo cited by WFB, it should qualify as safek treif in the same sense that a koy is a safek chaya safek behema. In sum, tzarich iyun.
Sea Sponge does not have fins or scales so it is not kosher. Please see Vaikra 11:9-13. It says of all living creatures, not just fish.
9 These may ye eat of all that are in the waters: whatsoever hath fins and scales in the waters, in the seas, and in the rivers, them may ye eat. 10 And all that have not fins and scales in the seas, and in the rivers, of all that swarm in the waters, and of all the living creatures that are in the waters, they are a detestable thing unto you, 11 and they shall be a detestable thing unto you; ye shall not eat of their flesh, and their carcasses ye shall have in detestation. 12 Whatsoever hath no fins nor scales in the waters, that is a detestable thing unto you.
It does not matter if it is an animal or plant since inedible things are kosher
I do not need to bring a source that a sea sponge is not edible until someone claims otherwise
Now, food which even a dog won't eat loses its status as food. Halachically, it's no different than stones or dirt which are you allowed to eat!
My edit (Excluding things like vodka that people do eat, but dogs to not (dogs are only a measurement on things that even humans do not eat)).