The "padding" AKA chamois is a vital guard against chafing-related injuries for anyone who intends to ride appreciable miles on a bike, and I would highly recommend wearing some garment with a chamois for any ride you do. For cold weather riding when simple shorts do not suffice, there are a number of different options. You can:
Wear proper cycling shorts under your chamois-free tights. This provides you with an additional layer of warmth without sacrificing the protection a chamois provides.
Buy leg warmers to complement your cycling shorts. Leg warmers are just an insulated sleeve that goes over your leg and runs from the ankle to just below the crotch. When you say you spotted other cyclists wearing tights under their shorts, it is much more likely that they were only wearing leg warmers. This provides them with the added leg protection, without a layer of material in between their body and the chamois.
Buy tights with a chamois. These are designed to fully replace your shorts, rather than complement them.
Riding any extended distances without a chamois is ill-advised because of the numerous health complications (that's a very bad part of the body to develop open sores), and when you do wear a chamois, it should always be the innermost layer, adjacent to the skin. Whatever else you wear to keep your legs warm just depends on your budget, the temperature, and what you find comfortable.