For TFS 2010, adding a state can be done and yes, it's pretty easy if you use the TFS PowerTools.
This MSDN blog entry provides quite a bit of detail for the Agile task board.
And this blog entry also provides some step by step procedures to do so.
So, with TFS 2010 and TFS Powertools, it's pretty easy.
For TFS 2012, it's not as clear.
This SO answer says both yes and no, with the accepted answer saying yes and providing some basic steps.
This SO answer links to another tutorial and says it can be done but the editing may be with the raw XML and not as pretty as you might like.