In general relocation reimbursements are done one of two ways.
They pay your expenses in allowable categories or up to a company set limit in those categories; and if you meet the time and distance rules from the IRS they are tax free.
They pay an flat amount and you either pay for moving expenses, or spend it on whatever you want. Those program aren't tax free.
You will have to get estimates for how much it will take to get you and your stuff to the new city.
In general the amount of money they can pay tax free for shelter is very limited if they want to keep with the tax free program. Of course with a flat amount, and the mention of after taxes tells you they aren't keeping it a tax free program.
The IRS publication 521 Moving expenses explains what is covered and how to handle the situation if your expenses are more than the reimbursement.