They are indeed legal, and are great folks. Steam keys can be sold by third parties at any price that the developer wishes to agree to, when it's a developer's game. In other words, it's not like you getting a bunch of free keys and then selling them for some low cost.
GMG works just like any other distributor, and in fact Arcen is partnered with them. We give them steam keys and tell them the price we want to sell at, and periodically we agree to do promotional sales, just like we do with Steam. The steam platform is the delivery vector, but otherwise Steam is not really involved in the transaction between the developer, the customer, and GMG.
It's the same principle as HIB. The developer gives Humble the steam keys, and then there is a PWYW for customers, etc. But aside from providing the steam keys, Steam is not involved there.