How do hairdressers expect me to behave, how can I refuse them and wait for a particular hairdresser without this being perceived as rude or unusual?
The polite approach is to express a positive preference for a certain person rather than a negative preference for another: when you arrive, state that you would prefer to wait until Mark or Sally are available because you liked the haircut you received in the past. This sort of preference is normal, and by posing the request up front you don't have to directly reject anyone else.
hairdresser = sales = service + customer satisfaction (about the technical part AND the human part).
So, AFAIK, and almost everywhere around the world where I've travelled (but a very few individuals, the same kind of "bad person" you can meet anywhere, in any country, in any service area...), the sales person will do their best to provide you with the best they can do/afford/offer. This can be less when you're just a stanger passing by (or a tourist), and more when you're a regular costumer. Which you are, as you say.
So, no, asking and expressing your preferences is not rude. It's even often expected, because the sales person will know that if you come back, it's because you enjoyed the service AND the person providing it. That's what they want and need: provide you with a service so that, pleased with them, you'll come back. Bad haircut or bad person means almost eveytime "never see me again"; and they need you back again for the business.
Therefore, I wouldn't worry too much about that. You're fine when expecting/asking for someone you know and like when they take care of you.
If you don't want to have this "problem" again, use the tools hairdressers provide to their customers : phone and appointments. 1. you can call before, and ask for Alice/Bob, and at what time they can cut your hair. 2. you stop by the salon, and ask them directly ("Sorry, I'd like my hair cut by Alice/Bob. Is it possible to come back later? And if yes, at what time? Thanks").
I've done that (Western Europe: England / France / Belgium / Spain), and still do it, and never had/have a problem. Even more in the US at the time, the lady answering the phone or greeting you WAS asking for "the 3 W = what, when and who".
I'd suggest asking before you get "trapped". Don't wait for an answer to a question you didn't ask. ASK what you need, how, and by who. It's easier, because, for the customer's satisfaction, they will (should) do whatever they can to please you :)
Last but not least, if you want to refuse, just deflect. Don't say "NO" to Steve/Jenny, but rather "I really enjoy last time with Alice/Bob, is it possible again?". And if it's a "just walk-in and wait / no appointment" salon, you keep the same request and just add: "...and how long would it take?". It's neither rude nor unusual.