Are you running Vista? If so, go to "Control Panel," then "Personalize," then select "Change desktop icons" on the left panel.
Simply make sure the Recycle Bin is checked and you should be good to go!
If you're running XP, then you'll have a bit of a headache on your hands. Try either TweakUI (like mitche323 said above) or try an extensive Google search on the problem.