First you purchase the land, and then you hit the housing menu in your actions area and it asks you what kind of deed you want to purchase. This is where "Wood, stone or Brick" come into play. The Deed costs a flat 1 million gil and you get base housing design for it. However, you can't really change the outside walls and roof much unless you have a mansion (large house) - because all the updated walls and such are for mansions.
edit: I decided to put up a highlight from my stream. You can see it here. Don't mind me wandering over to the info NPC, I had no idea what I was doing.
http://www.twitch.tv/eriatarka12/c/3500263