Many newer computers have the Stereo Mix device disabled by default, and you need to enable it using the instructions from:
I'm running Windows 7 64-bit native on a MacBook Pro. I found out that Apple have disabled the Stereo Mix device at the hardware level and it can't be enabled using the instructions above. After some research, I found a good solution to the problem.
VB-Audio Virtual Cable creates a virtual cable in the computer, routing a playback device to a recording device, all digital without quality loss. It is released as donationware, in contrast to Virtual Audio Cable which does the same thing for $25.
Download the install package and run it as administrator. Then goto Control Panel -> Sound. Select the Playback tab, select the CABLE Input device and click the Set Default button. Select the Recording tab, select the CABLE Output device, click the Properties
button. Select the Listen tab. Here you can choose whether or not you want to route the music to the speakers, headphones or some other device. I would NOT recommend selecting Default Playback Device or CABLE Input... :-)
When running music though the virtual cable, my MacBook Pro does not switch between speakers and headphones automatically depending on whether or not a plug is inserted in the headphones jack. It's just a minor inconvenience but might be good to be aware of.
Fire up Spotify Recorder, select CABLE Output as device and off you go!