Recommended software

Music production can be as expensive as you want it to be, but at the same time it can also be totally free. Don't be fooled into thinking that expensive tools will make the best end-product. In fact if the raw source materials are not good enough (you), the result might even be worse.
However, for some people the "best" options are usually commercial grade "you get what you pay for..." or some BS like that. And let's be realistic here: piracy is always an option. That being said, piracy should only be reserved for hobbyists. If you intend to get serious and profit from your music, you should absolutely support (and avoid getting sued by) the people behind products you believe in by giving them your business. General comparison of most of the commercial DAWs. [Outdated]
== DAWs ==
The main software you need is called a Digital Audio Workstation, or in short DAW. Most of them work and look like a visual, non-linear multi-track recorder and a studio mixing desk: Multiple tracks are layered on an horizontal timeline and mixed together for the final output. These can usually be either recorded audio (waveforms from microphones or real instruments) or command data for digital instruments (either real, external ones connected to the controlling computer, or virtual ones that are implemented as real software). The latter is usually in MIDI format. There are notable exceptions to this paradigm: trackers and what could be called grooveboxes or music production machines.
Trackers evolved from the game development and demoscene in the 16 bit homecomputer era (Atari ST and Amiga). The most notable difference between the horizontal timeline in DAWs is that a track is split into patterns (short segments strung together) which are each recorded on a vertical timeline.
Grooveboxes and music production machines evolved from the first digital sequencers, either dedicated machines or built-in sequencers in music instruments like keyboards, drum machines or samplers. Coming from hardware the approach to music making is more hands-on and tactile, either in the form of a dedicated machine (like the Akai MPC line) or an hardware controller (like NI Maschine).
Here is a list of recommended software that is preferably available for the 3 main operative systems (Windows, MacOS and GNU/Linux). Most of them are totally free or have a very lenient demo version. Also, it includes a short description and a list of about 5 favorite music genres that are produced with each program, but as a matter of fact you can produce almost anything with all of them.
*Audacity
: Simple, easy and powerful. This program is good enough for recording live input such as a microphone or electric guitar, and importing from other sources. Then cut, copy and paste it into an arrangement. Finally, process it through effects and plugins and export to your favorite audio file format.
: Audacity is primarily ideal for recording instruments, voices, or ambience (such as field recordings). It's not ideal for mixing or mastering, though. You should look at FL Studio or Pro Tools for that.
: Favorite genres: Vaporwave, spoken word, musique concrete, garage rock, grindcore, anything lo-fi or rough.
*Reaper
: This DAW gives other DAWs a run for their money. It can handle everything with a minimal footprint in your system and is very configurable. Similar to what Audacity does, but with the inclusion of midi editing. Automation for almost any parameter in your plugins, live effects processing and non-destructive mangling of wave-forms.
: Keep in mind that Reaper uses the same layout as a modular synthesizer.
: Favorite genres: Can do what all the others can and more!
*LMMS
: Fruity Loops alternative, it can even load native .flp files. Throughout the years Fruity Loops has come a long way and today it is quite advanced, however sometimes it can be too much. LMMS is similar to FL in the way of editing and arranging your track but with a less cluttered GUI and with many built-in synths and generators. Many people told me the only reason they wouldn't use LMMS is that it can't export midi, while that it's true there is a program called flpxtract that solves that problem.
: Favorite genres: House, hip-hop, synth pop, techno, wubstep.
*Hydrogen
: Not a full DAW per se, but mainly and exclusively used for sequencing drums in a visual and modular way. You can control the dynamics, layer samples and give it a humanizing twitch that makes the drums sound natural. Also, thanks to its modular way of sequencing patterns, you can arrange the parts of your song in a breeze. Finally, export it in midi or audio file and import it into your DAW for further editing.
: Favorite genres: Drum solos and moar cowbell.
*Renoise
: Now, for some people it might be the first time they see this paradigm of music production but it is quite unique that can fit certain purposes very well. It is called a "tracker", they have their origins in the demoscene, thanks to trackers it was the first time regular people didn't need a complete studio to produce music, just a computer and some samples or an audio chip. In other words, trackers are vertical and modern style DAWs are horizontal. Renoise specifically has all the DAW features of the previously mentioned programs, minus the sample waveform visualization. This can mean a hassle when working with vocals and live instruments recording but not impossible. Renoise is perfect for electronic music, specially for genres like drum n' bass and chiptune, because of it's beat precision and micro level of parameters edition.
: Favorite genres: Jungle, drum n' bass, break core, glitch, chiptune, doskpop.
*Sunvox
: Quite similar to Renoise but introduces a modular way of arranging everything, from synths effects, gates or eqs, to the position of phrases in the timeline. Also it includes many built-in synths that might not have many presets but powerful enough if you know what your tweaking.
: Favorite genres: Minimal electro, chillstep,chiptune, ambient, glitch. 
:* Live
Often referred to as Ableton (The devs), Live is one of the more utilitarian DAW's as it can blur the lines between performance and production. For a long time Live was considered quite a unique DAW as its primary focus was being a groovebox for DJs to trigger and effect loops. Since then it's evolved to accommodate production and is one of the most popular DAWs on the market. Along with a traditional arrangement view, Live uses a 'session view' in which loops and samples can be stored and triggered by mouse or from a controller. There are several controllers out there designed to use the session view like the 'Launchpad' (If your a faggot) and Akai's APC series, Ableton do their own controller called 'Push'. If you're a DJ looking to get into production Live is one of the best options out there (Unless you wanna try Bitwig) although it's great for just about anyone looking to get into production, the learning curve is a little steeper than most DAWs due to the alternative workflow but it's totally worth it for the in-built plugins and effects. If you purchase the 'suite' edition Live will come with a variety of synths and samplers that are pretty freaking awesome, you probably don't need all these as they can be replaced with free VSTis although the stuff that comes in the standard edition is well worth your money. The drum rack can load up 132 samples so you'll probably never need to go sample hunting again and the audio racks make creating automation macros a breeze. It can handle multi-track recording as well although from my experience it can only handle about 2-3 armed channels at a time.
Favorite genres: Pretty much everything
*MuseScore
: A more classical approach to music production. With this you can transcribe music by using notation symbols. Similar to what you have in a music book full of music sheet. With this program you can compose for as few instruments as one note in a triangle, to a grand piano, to drum kits and so on. Very compatible with midi and it looks gorgeous when printed on paper.
: Favorite genres: Classical, acoustic, orchestral.
*FL Studio (aka Fruity Loops)
: Although FL Studio is primarily known for producing EDM, it can do so much more! The DAW comes with a batch of Image-Line made VSTs, which are each super unique in their old ways, and also a bunch of drum and vocal samples. Although it can be a bit confusing to learn at first, it gets very easy to use. It's also good for MIDI Out, and is super third party-VST friendly.
: This DAW is recommended for post-production, mixing, and mastering, although recording in it isn't really that ideal.
: 
: Favorite genres: Electronic, experimental, anything else.
*Gleetchlab 3
: "A realtime modular composition and processing software for sound design and experimental music," Gleetchlab is a sort of of odd middle-ground between DAW and plugin, emulating the workflow of live tape recording/sampling and modular patching to give a unique 'organic' feel to digitally creating music. There is no writing of midi data, no built in VSTi's, and most importantly no saving of projects. To create a composition in Gleetchlab means loading up your samples, patching them into the matrix, pressing record and performing the piece live, though the intuitive design of the program makes this task less daunting than it may seem. Though it is best suited for 'experimental' music or composition which does not require sticking to a strict tempo or song structure, Gleetchlab is also a great tool for final touches on a song or processing individual tracks for a structured project already mapped out in a traditional DAW.
: Favorite genres: Ambient, glitch, IDM, minimal electronic, metro-ko.
: 
Have no doubt that these programs are the cream of the crop in their categories while at the same time being free or almost free. Also please don't be confused about which one to use, with time and experience you will notice that you don't need a swiss army knife program but you will have to use all of them to take advantage of their benefits and have the best results. For best results: RTFM!
== Plugins ==
Modern DAW software can be extended in functionality to modify and/or generate audio by plugins. They usually fall into two categories, although there are gray areas like vocoders:
#Generating sound (as in synthesizers, samplers and drum machines)
#Modifying sound (effects and filters)
Plugins come in many different API formats, and not all formats are compatible with any DAW software (and in extension, with the bit size used by the DAW: 32 bit or 64 bit, although the bit size problem can be solved for some plugin types by so called "bridges" like jBridge or 32 Lives). Some are even very exclusive by design. The most common plug-in types you can come across:
* VST - Virtual Studio Technology from Steinberg. There are multiple versions (current is VST 3.5), but most DAWs can handle at least VST 2 plugins. (Windows, MacOS, GNU/Linux)
* AU - Audio Units developed by Apple for their CoreAudio low level, low latency audio API. Therefore extensively used by GarageBand and Logic Pro (MacOS exclusive)
* RTAS - Real Time Audio Suite by Digidesign (now AVID) for their Pro Tools line of DAWs up to version 10. 32 bit only. (Windows, MacOS)
* AAX - Avid Audio eXtension also by AVID, exclusively from Pro Tools 11 upwards. Supports 64 bit. (Windows, MacOS)
* Rack Extensions - Exclusive plugin API for Propellerhead Reason (Windows, MacOS)
=== Suites/Packs/Compilations ===
SampleTank http://www.ikmultimedia.com/products/cat-view.php?C=family-sampletank (Windows, Mac-OS)
A dedicated sound library of instruments, synths, guitars, bass, and drums. It is for the beginner as well as veteran artists who like to have a complete pallet of sounds from western classical, oriental styles, African influenced percussion, to modern day electronic and pop music. Each sound is categorized for quick navigation and much more.
mda-vst (Windows, Mac-OS, GNU/Linux)
Awesome suite of plugins and specially its instruments (Piano, DX and Juno synths).
Insert Piz Here (Windows, Mac-OS, GNU/Linux)
All the midi manipulation you could ever want.
Togu Audio Line (Windows, Mac-OS, GNU/Linux)
Free high quality instruments and effects with a user friendly interface. Also two amazing synths (FM Bass and Juno synths) for reasonable pricing.
Calf Studio Gear (GNU/Linux)
Contains a lot of instruments and plugins. Their GUI are specially good, easy to use and very detailed.
Bristol Audio Emulations (GNU/Linux)
Huge number of synthesizers emulated as close as possible to their real-world physical counterparts. Recommended to be used with MonoBristol.
Synth1 (Windows, MAC-OS)
One of the most popular, free software synths.