In general, you can start doing undergraduate research as soon as you find a researcher willing to take you on. However, most lab research does come with a learning curve, and it takes most students at least 6 months to a year to become competent enough to really handle projects on their own.
As for starting out, there are two major things you could do. First, you could look at a list of job openings and try to land a paid position. Obviously, the pay is a benefit, but many of these jobs will require quite a bit of dishwashing and the like and very little opportunity to contribute to the lab's research. The benefit is that if you work in a lab this way, you have the chance to impress your PI and graduate students and it may be easier for you to convince them to keep you on as a research assistant (although you probably won't be paid once you make the switch).
Your other option, as was mentioned above, is to search the department websites and email people you are interested in working with. This will get you involved sooner, but it may be harder to break into a lab this way, especially if your science background is limited.
As for the benefit of a strong science background, I think it really helps when you are trying to find a lab, and when you finally get around to participating in planning projects and looking at data (usually at least a year down the line unless you have a strong background or are very lucky). Any lab will teach you how to perform the techniques you need, so a science background isn't vital with respect to technical skills.