To unlock the fortune teller shop, you or any other residents of your town need to have Katrina tell your fortune 20 times. You can even go to other towns and visit Katrina there. This helps increase your fortune count more quickly since Katrina will only show up in your town up to once a week.
- - - Post Merge - - -
I've got heri. Planning to get twenty then visit my one
The part about going to other people's towns with Katrina in it for fortunes is a red herring. Katrina's a unique special visitor and will only offer you the public works project in your town with your residents after 20 fortunes. Going to other towns doesn't count.