When you deconstruct a building do you get back all of the resources used to construct it? When I start moving to Stone houses, would it be better (assuming I've got the Labor) to build a new house and deconstruct the old, or upgrade, or are they the same efficiency?
No, you don't get back all of the resources, you can reclaim only a part of it.
Personally, I start to increase the number of people with Wooden houses. Then, if there are enough people to gather all the needed resources, I start building Stone houses.