A winch will benifit from a bigger battery but it not ususlly required. Make sure all of your battery cables have good connections, and are large enough. When you are pulling hard a winch will pull a lot of amps and kill any battery in a hurry. The best thing you can do is a series of short pulls with a few min in between to let the winch cool and batt charge.
When using your winch stop after a few min and relax the cable. Touch the winch motor and battery cables carefully. They should get warm, if they get too hot to touch you need more battery, better connections, or both. A winchs worst enemy is heat.
I have been very impressed with the harbor freight winches that I have seen. Slow, but reliable.