Be sure to scroll down... there may be more than one question on this page!
You can definitely paint over wallpaper, but I have mixed feelings about it. First, the seams will show through the paint unless you carefully coat them with a skim coat of wallboard compound to hide them. Second, you must use an oil based primer to seal the paper, or the latex paint could cause the wallpaper paste to soften, causing the paper to "bubble". Another "hidden" problem is that many wallpapers have a texture... sometimes not very noticeable until painted. Flowers, anyone?
Even if the paper is vinyl (which generally does not let water through) it is wise to prime because using a good oil-based primer-sealer will insure that the paint will stick to smooth vinyl surface.
The reason I don't suggest painting over wallpaper is that if the wallpaper begins to fail, the walls will begin to look very ragged. The repair is not difficult… simply cut out all the loose areas and smooth them with wallboard compound. Since wallpaper failure tends to be progressive, this process of failure/repair will continue on and on over the years. If you spend the time now to strip the paper, you save yourself future disappointment.
Once you paint, the removal process becomes much more tedious and difficult, since the paint has removed any porosity in the paper and also stiffens it by adding more thickness to the wall. The more coats of paint, the worse it gets!
Nowadays, with the high quality chemical wallpaper strippers available, removing wallpaper is not as much of a chore as you might think. Messy, yes, but not catastrophic. I have an article at the site that discusses some of the issues in wallpaper stripping.
It is always difficult, and sometimes impossible, to remove painted-over wallpaper without damaging the walls... especially if your walls are wallboard or a similar product. Plaster walls can take more moisture abuse and can stand more abuse. That is why the number one choice is to just leave it on the walls. With the proper repairs, all but the most awful wall surfaces can be restored to their original smooth glory!
The general procedure is to cut out all loose areas of paper and level the walls with wallboard compound, as if you were fixing shallow holes. You can similarly cut back loose seams and fill them. Once you do all the repairs, a coat of an oil-based primer is required to seal the walls. If you use a water-based primer, you may cause more of the wallpaper to release where you don't want it to! Also, though water-based primers have really improved over the last 20 years, they still tend to dissolve stains and carry them to the surface of the paint, leading to possible bleed through into your finish coat.
Removal of the paper is another more serious and more difficult task. Paste dissolving chemicals and/or a steam wallpaper remover will be your tools of choice in this endeavor. Of course, for the chemicals or steam to get to the adhesive beneath the paint/paper collage, you must somehow mechanically pierce the paint film. One old-time method is to use a stiff wire brush to abrade the surface of the paint and paper. Fast forward to the 20th Century… there is a retail product called the Paper Tiger that does this a little more neatly and easily. The Paper Tiger is a small hand-held tool that has hundreds of small pins attached to wheels. Rolling it over the surface of the wall introduces hundreds of small holes, usually deep enough to penetrate the surface but no so deep that you will require extensive wall repair afterwards. This product is commonly available at paint stores. The only drawback is that it may not fully penetrate through multiple layers of paint.
One you have sufficiently scored the paint film or paper, you can begin stripping the paper. You have two options. You can use a chemical wallpaper stripper, available at any paint or hardware store, which is mixed with hot water and sprayed on the surface of the wall. The chemical dissolves the paste and helps lift the paper from the wall. Your second, more severe option is to use a steam wallpaper stripper. Many paint stores and rental centers have these available, and will provide instruction in their use.
If the above methods fail you, the final and least desirable method would be to use a chemical paint stripper. Because these products are very toxic and possibly damaging to many other surfaces (including your body), I list this as a last resort when other less dangerous remedies have been ruled out!