Should the underside of a deck be stained?
This question is somewhat opinion based, but I'm going to answer anyway. If it's just a stain  or oil, rather than a more solid surface/coating finish like Varathane, you're probably OK to just stain one side.
With a solid coating, the problem is the wood will absorb moisture at different rates on the top of the deck from the bottom. This can lead to cupping, warping because wood &quot;moves&quot; with moisture.   If you are in an area that's dry most of the time, that would be less of an issue. Here in Western Washington, where we get a lot of rain and it can be quite humid at time, it's a consideration when finishing wood that will be outdoors.  Personal note: I would never again build a wood deck here, too much maintenance and short life span.
EDIT:  Giving credit to JimmyFix-it's comment, I'm adding to my answer.
Using a solid surface coating like Varathane or Urethane, etc. usually ends up being a disaster in just a few years if the wood is directly exposed to weather (rain, snow, sun), even without seasonal wood movement.  It will crack, peal, split and to re-finish you have to sand most of it off!  Penetrating oils also require maintenance every few years, but often just a good cleaning followed by application of the oil.  If you want that &quot;new wood&quot; look, it might require a light sanding first, but much easier to deal with than a solid surface coating. Products generically referred to as &quot;wood brightener's&quot; can also be used to remove stains, mildew, etc. but I find that a light sanding works pretty well.