Proper way to install subfloor in kitchen
We use to specify building paper between the underlayment and subfloor. About 10-15 years ago we stopped. Now, we worry about moisture (vapor) getting trapped between the underlayment and subfloor. 

Nail or screw: Either...the key is to drive 100% of the fasteners flush or slightly recessed.  (Be careful the head of the fastener does not "lift" the wood around the head.) Screws hold better (won't back out) but harder to drive flush with top of underlayment. Power-driven nails are fine, but depth will vary due to consistency of compressor. (When the nail-gun is used a lot in a short time, the compressor will be slightly "weaker" and a few nails won't be driven to same depth, until the compressor turns on.) Hand-driven nails are ok, but use ring-shank nails. 

Space between sheets of underlayment: Yes, it is recommended....about 1/16" space or less. 

Make sure you follow the flooring manufacturer's recommendation when installing your floor covering. Most laminated wood flooring manufacturers recommend a vapor barrier on the underlayment, but read the instructions carefully.