You can go to any shop that instructs to do your checkout dives. Even if they're not a NAUI shop. Your certification will end up with whichever organization the shop/instructor is affiliated with. So, if you do your checkout dives with a PADI shop, you'll end up with a PADI certification.
I recommend Chuck and Robbie's Scuba. They're a PADI shop and as good as they come...