They came from the Mushroom Kingdom, being residents that joined Bowser.
A mushroom who betrayed the Mushroom Kingdom.
– Super Mario Bros. manual
They are inspired by mushrooms. Specifically shiitake mushrooms:
We decided that that we should make an enemy that you could easily squash with a single blow. That's why we made it so that the first enemy the player would encounter would be a Goomba. But we created it right at the very end. [...] It's a shiitake mushroom!
– Iwata Asks: New Super Mario Bros. Wii
As an aside, in Japanese they are called Kuribō, which means something like "chestnut person". While presumably this refers to the colour, the design in Super Mario World was of a literal chestnut rather than a mushroom.
click images to enlarge