I doubt states would be concerned about taxing relocation benefits specifically because it might dissuade people from moving to the state. It would be a tiny tax liability relative to other tax liabilities that already vary such as income tax, property tax, and sales taxes. If those differences do not dissuade people from moving, then a one time ~5% income tax on $5k to $20k of moving expenses is not going to move the needle.