R. Yosef Albo, Sefer ha-Ikkarim 3:1, writes:
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. However, this does not resolve the question, because it is not clear how something between animal and plant should be treated (unless we should be machmir a la bein hashmashot according to the view that it is both day and night).
On the other hand, the Arizal (Shulchan Aruch HaArizal, Orach Chaim 167:14) and R. Yaakov Emden (Zoharei Yaavetz, p. 36) write that a sponge is intermediate between inanimate matter (domem) and plant (tzomeach). If so, it should be kosher.
Support for the idea that a sponge is considered a domem can be found in the Raavad (Hil. Tumat Met 20:5). The Rambam rules that the rule of absorbed tumah (tumah beluah) applies only to a living creature. The Raavad asks on this ruling from the Mishnah (Keilim 9:4) which states:
ספוג שבלע משקין טמאין ונגוב מבחוץ, ונפל לאויר התנור, טמא, שסוף משקה
A sponge which absorbed impure liquids, [even if it] is dry on the outside, and fell into an oven, [the oven is] impure, because the liquids will emerge.
According to the Raavad, from the fact that this Mishnah needed to invoke the reason that the liquid will emerge from the sponge, we see that otherwise it would have been tahor. This must be because the rule of tumah beluah applies even to a non-living creature. This proves that the Raavad considers a sponge to be a non-living creature.
Note that the Yerushalmi cited by @Alex which states that one who removes a sponge from the water on Shabbat violates the prohibition of kotzer does not prove that the Yerushalmi considers a sponge to be a plant--because the Yerushalmi (ibid.) is of the opinion that one also violates kotzer for removing a fish from water (רבנן דקיסרין אמרין הדן דצייד כוורא וכל דבר שאתה מבדילו מחיותו חייב משום קוצר). Obviously, the Yerushalmi maintains that one can violate kotzer even with regard to an animal.