He states that an aunt of hers traveled from Australia to Jerusalem to help take care of her after the death of her parents. This must have happened in the 1870s, more likely the first half of the decade. How would I go about finding what ships traveled from Australia to that part of the world, including possible transfer points such as Alexandria? Are there passenger lists available online?
Given that the dates you are looking at postdate the opening of the Suez Canal (which opened in 1869) it's likely that they would have taken passage on a ship going from Australia to Europe via the canal.
Most of the manifests I've looked at for ships following that route have a stop at Port Said at the northern end of the canal so that's where I'd be looking for somebody getting off and perhaps transferring to a local vessel as liners would typically head west towards the Atlantic at that point.
The majority of Germans arriving in Australia post 1866 (her birth) settled in South Australia or Queensland. You would need to search shipping records ex Port Adelaide or Moreton Bay (Qld) rather than the Outwards passenger lists for Victoria or NSW as suggested, remembering it takes 10 hours to drive in todays cars from Adelaide to Melbourne so unlikely they would sail from Melbourne.
Trove.nla.gov.au (free online Australian newspaper indexes) has no references to the name OLDAG so they may have only been here a few years.