Does anyone know how was the cow level discovered? I don't think the instructions were in the game guide. Was it hinted through either the game or the lore of Diablo 2? How did people figure out that you had to use a Tome of Town Portal and Wirt's PegLeg in the Horadric cube?
It was a rumor since the first Diablo. When Diablo II was released, Blizzard gave a screenshot of the Cow Level, hinting at its existence.
From there, people managed to figure out how to use The Horadric Cube to create the portal to the Cow Level simply by trial and error it would seem.
Diablo 2 was released June 30, 2000, and there is a post detailing the recipe for the Secret Cow Level created as early as July 4, 2000 here. That said, it doesn't look like it took players too long to discover it.
Straight from Blizzard:
The History of the Secret Cow Level
Many players of the original Diablo will remember the mysterious rumor that there was a Secret Cow Level. The story went that by clicking on a specific cow in Tristram a certain number of times, you could access a wondrous place known as the Secret Cow Level. There was, of course, no Cow Level in Diablo, but the legend was born. When StarCraft was released, it featured a cheat code, "There is no cow level". This was our way of officially confirming that there was, in fact, no Secret Cow Level. During the production of Diablo II, gamers often asked if there would be any cows to battle in the game. On April 1st, 1999, a Diablo II Screenshot of the Week featured cows fighting. People wondered if the screenshot was an April Fool's joke or if there really was a Secret Cow Level planned for Diablo II. When Diablo II was released, a quest item called The Horadric Cube allowed players to combine items to create new items. It wasn't long before players were experimenting with Cube combinations, hoping to find the keys to unlock new and powerful secrets. Eventually a recipe was discovered that revealed the most anticipated secret of them all -- the Secret Cow Level in Diablo II!