Google "brand spanking new" for more information. It's a phrase that simply intensifies the meaning of 'new'. "really new", "extremely new". There is also somewhat the connotation that the new thing is very clean from never having been used. "absolutely spotlessly new"