There's a LOT of different options for recording software, including some free options. The majority of people will use one of the following though, so go to the manufacturers website and download a demo and see which one suites you best. A lot of them do a "Lite" version, which should cost less money and shouldn't be too restricted.
Ableton
Pro Tools
Cubase
Logic (later versions are Mac only)
Propellorheads Record
Mackie Tracktion
The next thing you will need is some sort of audio interface. Again the best thing to do is hunt around on equipment websites and see which one suites you and your needs. Try and think 6 months down the line as well. It's hard but if you can save money in the future by spending a little more now, then do.
The audio interface will most likely be USB or Firewire, and will work with the software to give you a pretty solid recording setup. Most interfaces come with MIDI in and out ports, aswell as some sort of configuration for audio ins and outs. Usually a mixture of XLR and 1/4" jacks. Again the amount of each of these depends on your requirements.
In regards to the turntables. Well, again i'm afraid this is personal preference. If you want to learn to mix aswell I'd always suggest a set of Technics 1210s. They're an industry standard for a reason, and they will last a life time. However if you're just using a single turntable for sampling then I'd probably look into something that has the option to play at a variety of speeds including 78, on the off chance you want to sample some very old acetate
Cables... this will depend on what you buy from the above. The audio interface will come with the cable to connect to your computer I imagine. Most turntables use Phono cables (the red and white ones), and the majority of other audio equipment uses 1/4 inch jacks or XLR. Some also have the option of SPDIF.
Good luck, and always do your research before you buy anything. Read reviews from professional sources, forums, the website harmony central etc...
