Are you adding the criteria with Required = true? That would cause them to act as AND. On the other hand, if you add all criteria with Required=false it will probably match anything. I can't think of a way to require at least one. If you have other criteria as well so your query doesn't return too many results, you can filter the results to remove any hits that don't contain any of the property values. If not, I would do three different queries for the values and combine the results.
Edit: Now that I think about it I think it is enough to set Required to false. It won't include pages that don't match any of the criteria, so it should effectively work as OR.
I'm trying to do a fairly basic (I thought) property based search where I want to search for pages which have a property set to any one of several valid values. I'm using FindPagesWithCriteria and PropertyCriteriaCollection. Essentially I want to say "find pages where property=x OR property=y OR property=z". When I'm testing around, if I just add several PropertyCriteria to the Collection they are joined using AND as far as I understand, and that's not what I want. Haven't found a way to OR them together. Can someone please point me in the right direction?