You have to get a fortune from her tent (appears randomly in your plaza) 20 times, and it adds up between characters. So lets say you have 4 players in your game, and you all get a fortune, then you only have to have Katrina come 5 times to unlock the shop. Then I think the next time you get a fortune she'll ask you to make it into a public works project.