Verify that you have firmly inserted the USB cable into the headset jack on your iPod shuffle. The cable should be flush against the iPod, with no visible gap.
The image below on the left is an example of an iPod shuffle (4th generation) with a partially inserted cable. On the right is an iPod shuffle with the cable fully inserted and flush.
If the issue persists, please follow one of these articles, depending on the symptoms and operating system:
Mac OS X users: