The finish you get will depend on surface of the wallpaper.
If it's a smooth paper then you should be OK just to paint over it. You will notice where the paper is though as it will have a slightly different texture to the rest of the wall.
If it's a textured paper then you'd have to use filler to smooth it out first.
However, most wall papers have (at least) two layers. There's a backing layer and the surface layer (and possibly one in between depending on the quality of the paper). Even if you can't get the backing layer off the wall you should be able to get the top layer off. Soak it (as uSlackr suggests) - scoring it first with a sharp knife or scoring tool will help the water soak through - and then use a scraper to take as many layers off as possible. It's very easy to dig the scraper into the wall so you have to take care - don't rush.