How much are you willing to spend is the biggest question. Id come right out and say get Ableton Live. Or Reaper if u are short on cash. there are a million free programs out there to try to get ur feet wet with.
I'm not short on cash and I'm willing to get a good quality program.
If you're on a Mac and low on cash, get Logic Express. it will only set you back $199. Then when your ready and have more money upgrade to Logic Pro 8 (Logic Studio) for about another $299.
Also, Pro Tools LE is not that expensive (under $300). Personally though, I think Logic is the sh*t. Combine that with Ableton Live 8 - forget about it.
Thanks for the tips guys!
One last question...
What is a good website for tutorials on using Ableton? I want to get down all the basics.