Re: What noise gate?
I used the Boss one about 10 years ago. I found it easier to just turn off the guitar between song of when I wasn't playing. Then I started looking at all of the places where noise could get in and worked to remedy those.
I shielded the guitar cavities, used quality cables, use a pedal power supply with isolated transformers (like the Voodoo Labs ISO5/PP2) instead of daisy chains, physical placement of the pedals (wah next to power supply = tons of noise), use a good power conditioner, etc.
When recording I also keep the amp and pedal levels loud enough to give me the tone I want, but quiet enough that there isn't any more white noise than there needs to be.
Like others have said stay away from computers when recording. If I touch my laptop I get all kinds of weird noises coming through the guitar.
Are you running a lot of pedals? IIRC a buffer before your pedals can help knock down the noise because you are running a low impedance signal through your pedals which is more resistant to noise. Don't hold me to this I can't find my reference at the moment. I could be way off base.
As for noise gate recommendations my only experience is with the Boss NS-2. It did what it was suppose to do, but it wasn't for me. I've heard good things about the ISP Decimator, but I don't know how well it functions.