You are very welcome to the forums and we're happy to help you embark on your DJ career.
First of all, you really do want to consider your budget when starting. Apart from buying some of the cheaper entry level models of CDJs and mixers or second hand gear, controllers are probably the best way to go in terms of the functionality you get for the price you pay.
What software to pick? This is a very open question and boils down mostly to personal preference. I like Serato - I prefer the interface over Traktor / VDJ / Torq / MixVibes etc and it fits my needs perfectly. The best advice I can give you here is to trial each of the software packages and see which ones you like. If you local DJ store has different software setups, get down there and give 'em a test drive - see what you like.
One thing I think is important to point out when learning to DJ using a controller is to not rely on the visual display of the laptop - its all to easy to watch the waveforms on screen and then manipulate them to line up. Use your ears - train them to listen to the different tracks playing together and knowing which one needs to be sped up or which needs to be slowed down. It'll take a little time to get it nailed down but you'll sound find it easy.
There are a quite a few free resources online teaching how to DJ such as DJtutor (username ellaskins) on YouTube or visit DJsounds.com
Good luck and any more questions, please feel free to ask!