I helped paint a friend's house which had wallpaper over horsehair plaster. I'd get every bit of wallpaper residue off - any paste left will be noticeable after you paint. As for painting, we did one coat of primer, then one coat of paint, and that worked great. Horsehair plaster sort of drinks up paint, keep that in mind.
Also, consider using some spackle to fill in any large holes in the plaster. Horsehair plaster is also prone to crumbling when you pull off wallpaper.