The first thing is to get a good microphone, right? You are not going to get good sound out of a headset you use to play games or chat. If you are going to spend money, spend it there.
Software of all kinds is available, depending on the OS and hardware you are using, as well as your budget and level of intent (pro or fun?) Which is?
On the more costly pro side, you might consider Propellerhead's new Record. It ties very nicely into their Reason DAW, almost requires it actually to get the full feature set, so you have a complete studio that covers all the bases.
http://www.propellerheads.se/products/record/
If you are running Windows and want a very full featured DAW, one of the SONAR versions is going to be a very good choice.
http://www.cakewalk.com/
OK, those are my recommendations if you want to spend some serious money.
If you are looking for a choice on a budget or no budget at all you are definitely not out of luck.
On the very, very cheap side I use and can highly recommend Cockos' Reaper. It's cross platform, very light on disk space and resources (carry it around on a USB stick if you want!), very full featured, has a very active and helpful users group and did I mention it is really cheap? ;-)
Download and try it out!
http://www.cockos.com/reaper/
You can also check out the latest edition of the Computer Music magazine at your local bookstore. They include a DVD that has a lot of very nice free software including the full CM Studio. I happen to like Reaper better, but the CM collection is worth checking out.
http://www.computermusic.co.uk/
They also have some good free tutorials for beginners -
http://www.computermusic.co.uk/page/computermusic?entry=free_beginner_pdfs