Removing old linoleum flooring is difficult to do and as long as the current linoleum is flat and level then you should be fine laying a new surface on top of it. With that said though, when I remodeled my bathroom I did remove the old linoleum to put a new tile floor down. I actually found removing the linoleum fairly easy as I was able to peel most of it up in a single sheet and then I just scraped the remaining loose adhesive off the floor before putting down the backer board. (But I am not sure this would be the typical linoleum floor removal experience... maybe my linoleum floor was not properly installed originally.)
If you are going to keep your current linoleum down, the biggest thing to watch out for is that the new flooring will add height and could affect the thresholds and/or appliances. In the case of my bathroom remodel above, it is a good thing I did remove the old linoleum because the new tile floor is just at the level of the threshold. If the linoleum was there then I would have needed to raise the threshold.
Many flooring choices can be
laid directly over your old vinyl
flooring, as long as it is flat and
even. Keep in mind that anything
you add to the floors on top of your
old flooring will make the thresholds
that much higher too; it can also
impact any appliances that fit under
the counter, like your dishwasher. You
will want to consider this before you
do too much work. You may find that
the height change may cause a tripping
hazard.
Reference: http://www.theflooringlady.com/removing_vinyl_flooring_000805.html