Either Windows or Mac (or Linux). This decision generally will affect decisions on interfaces and software. Windows boxes are generally cheaper (although not necisarrily the case for high-end machines needed for audio and video), but more tempramental.
In order from cheap to not cheap: USB, USB2, Firewire, Firewire 800, PCI...You pay for more ins and outs and lower latencies. Your mic preamps and phantom power can come here, or from your mixer...depends how you set things up.
Not mandatory, but useful for most styles of music.
Very important. Should be in line, quality-wise, with how much you pay for your interface (and mixer).
You can get good headphones for $100 or so. My sister gave me some great Sony headphones long before I inverted in speakers.
First, you should choose a DAW. Some work on only one platform. You can get entry-level DAWs for under $200. You can pay $10,000 for the HD version of ProTools. Obviously, there are some good choices for under $500. Next, there are software instruments, effects, processors, patch librarians, and countless other tools. There are a growing number of open-source software titles available.
Like DAWs and Interfaces, the choices are staggering, but you can get a basic dynamic mic for $100 new, and a decent condenser for a little more. Seek advice from pros, as they will save you money.
There are drum machine style controlers, controllers that mimic analog mixing consoles, and just about any device that you can plug into a computer can be hacked to control musical processes.
In a small setup using software DAWs, instruments and effects, a mixer is not necesarry. If you have lots of outboard gear or speakers with no internal amplifiers, you need one.