These icons () show footnotes as tooltips... for some browsers.
I-580 California (link)
75.63 miles ; from I-5 near Tracy to US 101 in San Rafael. I-580 does seem a Frankenstein's monster of several freeways: the Altamont pass road, a rural eight-lane highway now serving hapless commuters for whom a two-hour commute is the price of affordable housing; a foothill freeway through Oakland; a new section (opened in 1990) past the shipping docks in Richmond; over a narrow bridge to San Quentin and Marin County.
Interstate System Designation
Interstate 580 from Oakland eastward is part of California's initial system of interstate highways, submitted by the state June 27, 1945, and approved August 7, 1947. The original proposal lists Modesto as the eastern terminus, because CA 99 was the original proposed location of Interstate 5.  No numbers were assigned until the mid-1950s.
In September 1955, the routing was moved (from the Nimitz Freeway, CA 17) to a proposed MacArthur Freeway, which was eventually built. In November 1957, the eastern end was moved with I-5 from Modesto to Tracy. In April 1978, CA 17 from I-80 to San Rafael was designated Interstate 180 -- a temporary designation. The CA 17 signs remained, because since CA 180 already existed.  Interstate 180 was changed to I-580 on July 7, 1983.
According to the FHWA, there are still 0.7 miles to be constructed on I-580, between milepost 12.50 and 13.20. The only notation in the July 1998 bulletin is "Alameda Spur". I'm not sure what that's about. 
Altamont Pass/Diablo Valley
The original four-lane divided Altamont Pass highway, from San Leandro eastward, opened on August 4, 1938, as part of US 50. I-580 is now eight lanes in that section, and needs them all. The pass is well known for its forest of propellers for wind power.
The interchange at I-680 in Dublin was originally a plain cloverleaf with collector-distributor roads -- underpowered for two busy freeways. A flyover ramp from southbound 680 to eastbound 580 opened there in February 2002, part of an interchange revamp that will finish a year early and $1 million under budget. 
I-580 between I-5 and I-80 was once part of a planned I-5W loop, along with I-505; that idea was scuttled in about 1964. Mike Ballard has seen a photo of I-580 signed as I-5W, which would have been around 1962. Sections of I-580 started opening in the mid-1960s. Until the mid-1980s (see below), I-580 ended at the "MacArthur Maze" interchange with I-80 at the Bay Bridge approach.
The $45 million revamped interchange with I-238, where I-580 eastbound crawls overhead like a centipede, was completed in 1989. Contrary to what was said here before, this is not the interchange featured on a Doobie Brothers album.
Originally four lanes wide through Castro Valley, I-580 was reconstructed some time ago with the intent to widen to eight lanes. However, environmental litigation held that up; meanwhile, Caltrans, needing to rebuild the highway anyway, went ahead with a compromise: build it eight lanes wide, but leave four lanes closed off. When the lawsuit was resolved, the lanes were opened. 
The 4.0-mile Richmond-San Rafael Bridge, double-decked and a narrow 2 lanes in each direction, opened in 1956 as part of CA 17. The 12.8-mile stretch of Highway 17 between I-80 and US 101 was given Interstate status in 1978 (as unsignposted Interstate 180), and officially became part of I-580 in 1983.
In 1985, new I-580 signs started going up. 580 was still not a freeway in the Richmond docks area, though plans had been in the works since the 1950s. The 6-lane John T. Knox freeway in this area broke ground in Feb. 1985. This non-freeway portion was signed "Temp I-580" until the freeway opened in 1990. 
Fixing the left exit at Albany
The I-580 exit from I-80, at the I-80/580 split in Albany, had been a
left exit since the US 40 days. In late July 1998, as part of
reconstruction between there and the I-880 interchange, Caltrans moved
the exit to the right-hand side. Confused traffic backed up for four
miles, proving that Caltrans need not spend much money on signs because
no one reads them. Here's a good quote from the San Francisco
Whatever Ms. Harris' other qualities, she wraps up a number of annoying Bay Area personality traits - she thinks she shouldn't have to read signs (and how dare Caltrans design roads without consulting her); she likes to flaunt her comparative wealth (a red Beemer, "4U2NV"); her time is more important than yours (she almost caused an accident because she didn't want to backtrack).
Fixing the 580/680 interchange
The interchange at I-680 in Dublin was originally a cloverleaf, dating back to the days when I-580 was US 50 and I-680 was CA 21. In 1986, Alameda county passed a half-cent tax increase to fund several highway projects, including a new flyover from 680 south to 580 east. At the time, this was the most congested traffic movement. 
In Feb. 2002, the project was completed, and it is quite popular.  However, now most traffic comes from the Central Valley to the South Bay, stressing the 580 west to 680 south loop; it seems a natural idea to provide a flyover there as well. Unfortunately, there are no such plans today. 
West of I-80, 580 is called the John T. Knox Freeway , after a State Legislator. Named by Senate Concurrent Resolution 50, Chapt. 78 in 1980.
Between I-80 and I-238, it's called the MacArthur Freeway, after General Douglas MacArthur of WW II and the Korean War. MacArthur Boulevard (old US 50) was named for the general in the 1950's.
I-580 (decommissioned) Nebraska (link)
This is a former numbering for what is now US 75 north of I-480 in Omaha. The 4-mile freeway would have connected two limited access roads, one to the airport, one to NW Omaha/Fremont. This route was actually signed I-580 for a while. However, federal interstate standards for the 480/580 interchange would have doubled the cost of constructing it. Omaha and the state declined, and removed the 580 signs on the 2 miles of existing freeway from I-480 to Lake St. 
At least part of I-580 was approved around 1976, and right-of-way acquisition was to start between Lake and Fort Streets in 1977. 
In fall 2004, Nebraska Department of Roads began reconstruction of the 480/old 580 interchange. Work includes removing ghost ramps to the cancelled West Freeway, elimination of left exits, and modification of roadways with inadequate design speeds. 
I-580 (future) Nevada (link)
4.99 miles ; future numbering for what is now the US 395 freeway in Reno. The official extent of I-580 right now is from I-80 to Del Monte Lane (SR 667) . The highway is obscure enough that question #43 of an online Reno Quiz: 100 Things Every Reno-Sparks Resident Should Know is simply: "Where is Interstate 580?"
Nevada DOT plans to extend I-580 southward to the Bowers Mansion cutoff at Washoe City by about 2007.  This will connect completed portions with the constructed portion near I-80 and a planned Carson City bypass, which will be complete around 2010.
If you're wondering: "wasn't this freeway already signed 580 at one time?" you're right: Interstate 580 appeared on some signs and some maps in the 1980s. Rand McNally maps in 1985 and 1987 marked I-580, but do not now. Surface streets approaching US 395 interchanges included I-580 signs for about a year during the early 1980s, but were taken down. (There were never any I-580 signs on US 395 itself or on I-80). 
Even today, small reference markers on US 395 say "IR 580." 
The idea for a US 395 freeway dates back to the 1950's. A Wilbur Smith & Associates 1960 proposal also called for an Outer Belt Highway where McCarran Blvd. is now.  The US 395 freeway in Reno opened in 1979.
Planning in Washoe County dates back to 1957. The first segment opened in the early 1960s, but environmental issues held up the Winters Ranch to Glendale Avenue segment, delaying work there until the 1980s. Opening dates:
Extension toward Carson City
Nevada had planned to extend I-580 to Carson City by about 2005, but this was delayed. NDOT's current plan for the Carson City Bypass as of fall 2002:
So what about the 580 numbering??
NDOT's position (fall 2002) is to sign I-580 from I-80 south through Carson City; i.e. to the end of the planned bypass freeway. This would happen when the highway is completed, around 2008. The state does not plan to sign I-580 north of I-80. .