Should I use a plastic moisture barrier underneath a new deck to help prevent rot?
I would not do the plastic vapor barrier as it will not do much to help. The area under the deck is open to the outside air and that air will dominate the moisture content of the air under the deck. In a crawlspace under a house, the air moisture can easily be dominated by the soil moisture and is one reason that a vapor barrier is used.

The tar paper over the joists and under the decking is a VERY GOOD idea and it is one of the best things that can be done to prevent decay of the joists. Use pressure treated wood of course for the joists and other framing. Wood rot likes moisture, especially standing water or nearly saturated wet conditions, and this occurs at joints such as where the wood deck boards bear on the joists and is also most exposed to the weather but not directly exposed to the air to allow it to dry out well. 

You can also treat any cuts into the pressure treated wood with liquid rot prevention treatment, as decay occurs faster at the end grain, and the manufacturer applied pressure treatment is greatest on the surface and decreases towards the center of the boards (the cut is into an area with less treatment). It's been a while so I don't have a brand to recommend, however the manufacturer or supplier of the pressure treated wood can make a recommendation.