There are several states with no state income taxes. Florida is one, as several people have verified. Washington state is another. The state of Alaska actually
pays you to live there - it's some amount based on the number of people in your family. Of course, they take that money from the oil companies, so guess who ultimately pays for that?
Also, Nevada, South Dakota, Texas, and Wyoming.
http://www.taxadmin.org/fta/rate/ind_inc.html