The user should not be forced to enter a postcode. There are valid cases for wanting to find a nearby store but not knowing the postcode. For example:
- I'll be honest and admit that I can never recall the postcode for my office, even though I've been working there for 3 years. If I have to give my office postcode, I have to look at my business card. Embarrassing to admit, but it's true. I very very rarely give out my office's street address, so I have no reason to remember the postcode.
- If I'm travelling, I have no idea what postcode I'm visiting. If I'm visiting from another country, I might not even know what the valid form of that country's postcode is.
- A couple of weeks ago, my father called me and asked me to help him find a local business. He was out, he doesn't have a smartphone, and the store that he was going to had closed and he didn't know where the next nearest location is. I didn't know which postcode he was in.
If your list of stores is long, only allowing the user to search on state would place a high cognitive load on the user to scan the list to find the store that is closest to them. In the case where I'm visiting from elsewhere, if there isn't a store in the city that I'm in, I might not know the area well enough to be able to figure out which is the closest store. Given the size of Western Australia, I'd be especially annoyed to have to open up a map application and look up each individual city or suburb to figure out which one is nearest.
I think that Target has a pretty good store locator. They have a single box wherein I can enter either my city and state, or my postcode (ZIP code, to Americans). Since Target stores might have different departments, they also allow me to optionally specify that I want a Target with a specific department. This might or might not be relevant for you; in the case of Target, it's a useful way to get meaningful results. Their store locator allows you to just enter a city, in which case it makes a guess, but they don't do a good job of showing alternate interpretations (Portland, Oregon vs Portland, Maine, for example).