A simplistic answer would be that it's a multiplier on how much money per paycheck to subtract from your tax withholding (taxes per paycheck), then at the end of the year you will have paid taxes on your income minus the amount of your withholding allowances.
If you get a decent (roughly 3% or more of your gross annual salary) refund you are letting the government withhold too much (and should increase your allowances), if you have to pay a decent amount of taxes at the end of the year then the amount withheld is not high enough (and should decrease your allowances).
I definitely recommend using the calculator that Stephen Cleary mentions, but I think it's just as easy to adjust it up or down by 1 or 2 each year based on whether you got a large refund, no refund, or paid taxes.
If you are disciplined with your money many experts advise to increase withholding allowances, save the extra in a safe short term interest account so that you earn money on your money and not the government.