For Federal, it's the taxable income as answered in How to base my income tax bracket?How to base my income tax bracket?
State has a similar process, but each state is different. e.g. some states do not honor IRA deductions, and some states permit a deduction for the 529 college savings account which Federal does not.
FICA and Med come off the very top of income with a couple exceptions - FICA has an income limit, in 2012, it's withheld only up to $110,100 of income. And - I believe certain deductions such as FSA (The "Flexible savings account" for medical expenses) may be pre-FICA deductions.
Edit - in case my wording was ambiguous - With the small exception of the FSA deduction, FICA/Med is calculated on one's gross income. FICA/Med does not reduce one's taxable income for Federal or state income tax.