How can I verify that one of two methods was called using Mockito?

Generally, if you're calling verify on a "getter" of any sort, you're assuming too much about the implementation. Mockito is generally designed for flexible tests (compared to "brittle" test that need to change even if the code is correct); your test should care more about whether the value is correct as opposed to which methods were used to get that value. A better solution might be to stub both getters to return a predictable value, and then use a normal assertion against the same value to ensure it plumbs through to the correct place.

when(mockFoo.getProperty("bar")).thenReturn("bar value");
when(mockFoo.getProperty("bar", anyString())).thenReturn("bar value");
// ...
assertEquals("bar value", new SystemUnderTest(mockFoo).getBarProperty());

Mockito's documentation spells this out:

Although it is possible to verify a stubbed invocation, usually it's just redundant. Let's say you've stubbed foo.bar(). If your code cares what foo.bar() returns then something else breaks (often before even verify() gets executed). If your code doesn't care what get(0) returns then it should not be stubbed.

That said, if this is a pattern you're required to support (or a method call with both overloads and side-effects) you can get a lot of information via Mockito.mockingDetails and MockingDetails.getInvocations, including invocations as of Mockito 1.10.0. You would need to loop through the Invocation objects to check against multiple methods.

boolean found = false;
Method method1 = Foo.class.getMethod("getProperty", String.class);
Method method2 = Foo.class.getMethod("getProperty", String.class, String.class);
for (Invocation invocation : Mockito.mockingDetails(foo).getInvocations()) {
  if (method1.equals(invocation.getMethod())
      || method2.equals(invocation.getMethod()) {
    found = true;
    break;
  }
}
assertTrue("getProperty was not invoked", found);

Note that this second solution is a little dangerous, as it does not benefit from automatic refactoring tools built into IDEs, and may be harder to read than some other solutions. (The above may also be missing calls to isIgnoredForVerification, markVerified, and other niceties.) However, if you foresee needing this frequently across a large codebase, then using Mockito's built-in APIs may afford you much more flexibility than you would have otherwise.

You could use atLeast(0) in combination with ArgumentCaptor:

ArgumentCaptor<String> propertyKeyCaptor = ArgumentCaptor.forClass(String.class);
Mockito.verify(foo, atLeast(0)).getProperty(propertyKeyCaptor.capture(), anyString());

ArgumentCaptor<String> propertyKeyCaptor2 = ArgumentCaptor.forClass(String.class);
Mockito.verify(foo, atLeast(0)).getProperty(propertyKeyCaptor2.capture());

List<String> propertyKeyValues = propertyKeyCaptor.getAllValues();
List<String> propertyKeyValues2 = propertyKeyCaptor2.getAllValues();

assertTrue(!propertyKeyValues.isEmpty() || !propertyKeyValues2.isEmpty()); //JUnit assert -- modify for whatever testing framework you're using