"I'm lucky that, except for a few rough spots, the wood is pretty even. Do I need to remove the paint completely or will the laminate stick to a roughed up side with some paint still on it?"
I would worry about the contact cement reacting with the paint and creating a gooey mess. As far as sanding and the grit that you use it would depend on what type of sander you are using. If you are using a belt sander, be real careful, they are pretty aggressive. If you are using an orbital sander, I personally start with an 80 grit paper (sometimes 60), as its less work, but its not bad advise to start with a 100 grit and see how it goes.