In 1972, Stanfurd University dropped the nickname Indians on the grounds that it was racially insulting and demeaning. (Around this time, some Native Americans had claimed Alcatraz Island--this might have had some effect).
The student body was asked to choose a replacement nickname, and picked the name Robber Barons (in "honor" of Leland Stanfurd, Sr.) as a replacement.
According to Mike Conte <conte@kerner.com> another choice was the Steaming Manhole Covers and Jason Christian <jason@gordy.ucdavis.edu> has reported that one other was the Master Card (which I wonder about since Master Card was Master Charge back then and is a name I've always associated more with USC than Stanfurd).
University officials were not amused with any of the choices, toyed with the idea of no nickname and several others (including the Thunder Chickens, which was a nickname for the 1970 Stanfurd football defensive squad) and eventually chose Cardinals after the color.
The Stanfurd Band introduced the Tree in 1975. (The redwood tree pictured on the university symbol is El Palo Alto, an old tree for which the city is named.) Officially, the Tree is the mascot of the Band, not the university as a whole.
During the week prior to the 1982 Big Game, Stanfurd announced that they were dropping the "s" from Cardinals, and that they would be named Cardinal so that people would be sure that Stanfurd's teams are named for a color, and not a bird. The Stanfurd Band took light of the name change by having someone dress up as a religious cardinal at the 1982 Big Game, though a different action by the band which occured much later in the game overshadowed this.
In the early 1980's, some Stanfurd alumni pushed for the return of the nickname Indians, and during the 1983 Big Game, Stanfurd players had little stickers of the old Indians logo on the back of their helmets. Nothing changed.
In the early '90s, the issue of picking a new nickname came up again. Stanfurd's bonfire rally in 1993 was moved from Lake Lagunitas (or Lake Lag as they call it) to another location because it threatened the habitat of the California Tiger Salamander. Some students pushed to change the school's nickname to Tiger Salamanders. On the gobears mailing list at least two alternate nicknames have been suggested: Hoovers, in honor of Stanfurd's most famous alumnus (and we all know what Hoovers do best) and Cry-Babies, because of the incesant whining after the 1982 Big Game and the recent exploits of Stanfurd alumnus Jeff Tarango.
One more note--speaking of schools with no nicknames, prior to their NCAA Basketball game against Stanfurd, Sienna adopted the nickname Saints, though they had no nickname before that time.
You may be asking "Why does a Cal fan know lore about Stanfurd?"---I can't answer that.