I only have their first names, maiden names, and know that they were born in Victoria, Australia. What is a way to locate these relatives.
For Australia you should view the current Commonwealth electoral roll this would only be effective if your female relatives have not married and still retain the same maiden name.
If they do have different married names you may be able to visit the Family history center at the State Library of Victoria and view past electoral rolls on microfiche to find the last result with original madien names to narrow down when married and then view past newspaper announcements from that period.
Your search is greatly complicated by the fact they are female, so may have changed their surname.
It's probably still worth searching the phone books: Telstra White Pages and Person Lookup AU. They may be unmarried, or may not have changed their name (although that is less likely for their generation).
The Victoria BMD registry does not have any recent data available to the public, their (paid) family history search only goes up to 1911 for births, 1942 for marriages, 1985 for deaths. It might be worthwhile checking the deaths on there, in case they died young.
I've had good success searching Google for the names of cousins, where the name is very unusual. They may have mentioned their maiden name, for example in a Facebook post. Try the name in quotes "Joe Soap" and also reversed "Soap, Joe" (the latter format is how they might appear on lists, such as a list of marathon race entrants).
Realistically though that's more useful for your generation, than your mothers generation. But I did find one 80+ year old relative mentioned in an online gardening club magazine (in Dutch), and others in golf club newsletters, so it's worth a try. Also look for them on Facebook - they may not be very active but their children may mention them.
Finally, they may have left Australia. You could look in the UK Phone Book or any other country where you think your family may have connections.