As an avid Skype and Gizmo user I have headphones with microphone to get the best sound quality possible. I used Plantronics .Audio 90 Analog headset connected to the microphone and headphone jacks on the Windows laptop.
After I switched to Mac I kept the same headset and was surprised to hear from my friends and relatives that the sound quality is very poor. At the beginning I attributed that to Skype running under Rosetta but things did not improve after the Universal version of Skype was released.
Only a few days ago I found that the traditional headphones do not work very well on Macs. In fact, on my Intel iMac I used the built-in Audio Line Input jack to connect headset microphone and it just does not work. See MacRumors forum for more details on this.
Long story short, today I connected the USB headset (Plantronics .Audio 550 DSP) and got the must better sound quality—I called my friends and they were happy to tell me that the background noises completely disappeared.
At $60 USD (retail), Plantronics 550 DSP is not the cheapest headset you can find but it is definitely worth it. Even if you get a different model, make sure it is USB.
Update (September 12, 2006): If you use USB-based headset, do not miss the SoundSource — freeware menu application from Rogue Amoeba. SourceSource lets you easily chanage the current input and output sources.