First the interface - there are many good fully assembled interfaces you can purchase. My favorite is the RASCAL from BUX Comm which comes in both kit form and fully assembled. The fully assembled RASCAL is $35, but if you are handy with a soldering iron, the kit is only $20 and is very easy to assemble. Everything is supplied including all cables, connectors, components, case and circuit board. The best features of the RASCAL is that it is a totally isolated design with isolation transformers and an optoisolator, and it doesn't need an external power supply! After you have it assembled, you can also use it for SSTV and other digital modes.
Now the software. There are many free packages out there. I recommend DigiPan for new users - it's simple and easy to get working. After you have had experience running PSK31, I recommend you run WinWarbler by Dave Bernstein, AA6YQ. WinWarbler will simultaneously decode three conversations at once, making it easy to monitor new DX while carrying on a conversation. For contests, I recommend W1SQLPSK which will decode 20 conversations at once!
Finally, where do you find PSK31 on the band? Well, the most popular frequency by far is 14.070 MHz. Please see my PSK31 Handout for other frequencies.
Once you have PSK31 working, try some other digital modes like SSTV, RTTY, QPSK31, Throb, Hellscriber and others. You can decode them all with some free software and the same interface you use for PSK31.
I'll look for your warble!
-David N9KT