How to install GNU-sed?
It would appear that the brew link process didn't successfully link from the Cellar to /usr/local/bin.

First, let's check that it installed. Try brew list and you will get a list of installed formulae. If gnu-sed is in there then it installed okay. If it's not, then run brew install gnu-sed again and you should be okay.

If it is in the list then try linking it and see what output you get. brew link gnu-sed will do this. It should link okay and you will be off and running.