Traditionally, when people build houses they cover the walls with one of two things: paint or wallpaper. Paint is easily applied and can be covered with more paint, but is generally a solid colour and uninteresting to look at. Wallpaper, however, can have intricate printed patterns and all sorts of nifty designs1, but it is a horror to hang, and before you can redecorate again you should remove it. Many people do not remove it, because removing it is a horror as well. Instead they paint over it or apply multiple layers of wallpaper, making a bad situation even worse.
At its most basic level, wallpaper is simply printed paper that is pasted to the wall. Over the years, variations have been created, including paper-backed cloth, paper-backed vinyl, just vinyl, and cloth-backed vinyl among others. Before you remove the wallpaper, you must determine what type it is. You do this by removing some and looking at it, front and back.
Paper is the oldest form of wallpaper, the most easily damaged, and the hardest to remove. Much of the advice you hear about removing wallpaper refers to this type. The paper must be soaked until the paste becomes wet, then the paper must be scraped off the wall before the paste dries again. You can rent or buy a steamer for soaking the paper. This is a slow and tedious process, but it may be the best method. Alternatively, you can use a spray bottle or sponge to wet the paper with hot water and white vinegar, but this tends to be messy. You can also purchase a wallpaper remover solution which helps neutralise the paste, but the vinegar and water seems to work about as well.
Lining paper, painted over with oil-based gloss, paint is a nightmare. You have to soften the paint (usually with a steamer), scratch the surface, then steam again to get the paper off.
Another nightmare occurs in old houses with sand-and-lime render. This has a horrible tendency to turn into sand and lime dust if not treated with extreme care. You have to be very circumspect when steaming, especially ceilings. The best method is to steam lightly until the paper can be scraped off with a sharp scraper, then wash off the residual paper and glue with sugar soap.
Vinyl is the easiest to remove, since you can usually just pull it intact off of the wall. However, paper-backed vinyl or the vinyl-treated 'washable' wallpapers need to be soaked as above, with the additional problem that vinyl is waterproof.
Before removing vinyl-and-paper wallpaper, you must pierce the vinyl so your water or wallpaper remover can penetrate to the paste. One method is to use a razor to carefully score the paper diagonally. However this tends to create strips or squares of wallpaper that can be very frustrating to remove, particularly if your score marks are very close together. If you are not careful you will also cut lots of diagonal lines into your wall. A second method is to sandpaper the wall with coarse sandpaper, with just enough pressure to pierce the vinyl. Finally, special tools can pierce the vinyl without damaging the wall, and tend to be easier to use than sandpaper.
Once the wallpaper is pierced, you must apply a solution. In this case, using a wallpaper remover solution is preferred, since in the time it takes the water and vinegar to penetrate the vinyl it is likely to evaporate. The solutions will help to break down the paste, so if they do dry you can just quickly wet the wall down again and begin removing the paper without waiting for the liquid to penetrate again. Steam will not be as effective as it is with plain paper.
In all cases, start by removing as much loose wallpaper as possible. If you can pull the vinyl off the wall just leaving the paper backing, do so. Otherwise, pierce the vinyl, apply the solution, wait the prescribed time, then remove the wallpaper by pulling from various directions and scraping with a wall scraper or drywall knife. If you are lucky and you used one of the vinyl-piercing tools, the vinyl will come off in complete strips, leaving the paper behind which then must be removed by again soaking, pulling, and scraping. Work on one section of the wallpaper at a time. As you remove the wallpaper, roll or fold it in on itself so the paste does not go everywhere (you should have spread a drop cloth before working with all this water and goop!). Do not be stingy with your liquid - reapply it as often as needed to keep the paper wet. Wet paper will come off more easily than paper that has been allowed to dry even a little bit.
When the paper is removed, wipe down the walls with a sponge soaked in water and a small amount of detergent to remove any extra paste. If you have a mildew problem, you may want to add some bleach. Wait for the walls to dry, then repair any damage caused by all the scoring and scraping, prime the wall and paint or paper it again.
Emulsion paint won't stick to wallpaper paste but walls are always sized with paste before papering (otherwise the paper falls off, especially if you paint over it). If you want to paint a wall which has previously been papered you can either clean the glue off with a hot solution of sugar soap and a mild abrasive (white pot-scourer is good); or cross-line (with the lining paper running horizontally and butt-jointing rather than overlapping or leaving large gaps); or best of all skim the surface lightly with pre-mixed joint paste, used for dry-lining and partitioning. This is ludicrously cheap from builders' merchants, and can be applied very quickly using a caulking blade (a piece of semi-rigid plastic about 12" long by 5" deep, with a wooden spine along its length. Smaller ones are easier to find but much less useful).