The first impulse of an unsophisticated rider who finds a saddle uncomfortable is to replace it with a softer one. This, however, is often a mistake. In the same way that the most comfortable mattress to sleep on is not necessarily the softest, soft saddles put the weight in all the wrong places, among other things.
Try sitting down on a desk, and leaning back a little. You'll notice that most of your weight is concentrated on two load-bearing "sit bones," or the ischial tuberosities. These are the structural elements of your body designed to carry your body weight when seated without pain or discomfort. Most cases of saddle discomfort arise when the weight is put on the soft tissues between and surrounding the sit bones.
Now imagine placing a soft pillow between the desk and your bottom. As you sit down on it, the fluff yields until the sit bones are nearly on the desk's surface once again. Now, however, you have pressure on tissues other than the sit bones from the pillow. Many saddle buyers are unaware of this, and department store saddles are designed to prey on such consumers. The fact that large springs are prominently mounted on the back, or that your thumb will sink right into the squishy top, makes Aunt Metilda say "Wow Geo-orge, look how com-fy this one looks! The seat on that Wal-Mart cruiser was always so hard on my poor tush!" meaning, of course, hard on tissues other than the sit bones.
In actuality, soft saddles are only comfortable for very short rides, and when you are on the bike for more than a mile or two they are much less comfortable than a real saddle. Women especially will find pressure on genitals to be uncomfortable, where they could have simply used a saddle with a cutout. Saddles with excessive padding and high-friction covers are also a common cause of painful chafing of the inner thigh, as rides become longer.
A springy saddle, or a soft one which doesn't keep your body the same distance from the pedals over bumps or through the pedal cycle, will disrupt your pedalling by causing the rider to bounce at high cadences. A springy or squishy saddle will also disrupt the proper seat height, which is a major factor in pedalling power.
Rather than getting a squishy "mattress" saddle, try getting a proper "racing" saddle. It's not just racers who will find them to be more comfortable and more efficient. Dial in your seat with respect to the tilt and position. Lower your handlebars and buy a bike with dropped handlebars for a less "upright" position (itself another gimmick for feeble Wal-Mart consumers), so less weight will be on your seat, and so that the energy of bumps is dissipated rather than being directed into telescoping your spinal cord.
Check out our article on finding a comfortable women's saddle from our section on womens' cycling.