The form below is the result of combing through PDF files from irs.gov to get an accurate picture of how federal payroll withholding tables changed through the years. I later tacked on tax tables to compare with the payroll tables to see how they lined up (which they do pretty well... with a couple exceptions that I'll get to). I've populated data from the years 1998 to 2013, and added a simple HTML5 interface for charting the results.
Choose a salary from the slider (if you don't see a slider control, the charts won't work with your browser - the HTML5 "range" input type currently only works in Webkit browsers and Opera), and then click married or single, to see the chart for that salary.
The code makes some basic assumptions for the sake of simplicity. First, the salary is taxable income, after other deductions such as 401k, social security, etc. Second, the tax line adjusts the salary down by the standard deduction (twice that for the "married" category, assuming "married filing jointly" is the filing status), where the withholding line does not. This appears to be the intent of the descrepencies between withholding and tax tables, that is, separating what your employer knows about you from what the government does. Your employer doesn't know about your mortgage interest, whether you'll file joint or separately, whether the child tax credit applies to you, how much you spent for college tuition, or any of the hundreds of other deductions or credits you'll talk to Uncle Sam about. They know what you contribute to 401k, how many dependants you intend to claim, and that's about it.