This video (https://www.youtube.com/watch?v=L8fVS78tvzU) says that seaweed is written like 海草、but Google Translate later told me it's instead 海藻, with 藻 as the second Kanji instead of 草. I know GT shouldn't be trusted, but I Google Image searched 海藻 and got pictures of seaweed, so.. can someone tell me which really means seaweed?
If you mean edible seaweed, 海藻 is right to use. Nori, wakame, mozuku, hiziki and mekabu are all 海藻. They look like http://bit.ly/1gfJick
In Japan, usually, people don't eat 海草. Dugongs like to eat 海草. http://www.arkive.org/dugong/dugong-dugon/video-01a.html
海草 is often used to mean 海藻 by mistake.
海藻 = seaweed,
海草 = spermatophyta living in sea (water).
For details, see -> https://ja.wikipedia.org/wiki/%E6%B5%B7%E8%97%BB together with https://ja.wikipedia.org/wiki/%E6%B5%B7%E8%8D%89.