Throw It In: Austin's "Stone Cold" moniker was inspired by a comment from his wife at the time; she handed him a cup of tea, and remarked that he should hurry up and drink it before it got "stone cold".
Mick Foley mentioned in his book how, at the time, Austin was searching for a suitable "cold" nickname to suit his character— and was very lucky for that one to come along, as the writers had been coming up with some stinkers. Foley mentioned Austin could have had the exact same personality, but the moment he was announced as "Chilly McFreeze", there wouldn't have been much hope.
Austin actually appeared on at least one TV broadcast as "Ice Dagger" Steve Austin. Which... isn't that bad of a nickname, really.
The WHAT? catchprase. He was calling Christian one afternoon and left a voicemail. He said "what?" every other line for some reason. Christian found it so funny (if incoherent) that he suggested that Stone Cold use it. The rest, they say, is history.
What Could Have Been: Austin and Pillman, former tag partners with a great relationship and great chemistry, could have had some legendary feuds over the years had Pillman not died at 35.
Austin was also supposed to feud with Mick Foley, with Foley being revealed as the "Higher Power". Foley declined, as Foley's numerous injuries had caught up with him at this point.
Austin was supposed to wrestle Hogan at Wrestlemania 18 instead of the Rock. Austin actually declined, believing that his style and Hogan's wouldn't mesh, and that the match wouldn't live up to the hype.