In early spring, birds appreciate a supply of suitable nesting material placed on a small high platform in the garden. Suitable materials are human or animal hair, small lengths of wool, bits of string, dry, soft grass, teased out cotton wool and clean carpet fluff or underfelt. Birds use a very wide range of materials for nest construction and lining. For example, magpies have been known to build nests entirely out of wire and plastic, probably because they were the most readily available materials at that particular site. It is best to observe, if possible, which birds are using the nesting material, because it may be that only starlings and sparrows are taking advantage of this supply.
Many birds nest in hollows in trees. You can use suitably constructed nest boxes to attract such birds to your garden. The Nest-Box Book, published by the Gould League, describes how to build and maintain nest boxes for rosellas, Red-rumped Parrots, Galahs, cockatoos, kookaburras, Barn Owls, Nankeen Kestrels and falcons, Grey Shrike-Thrushes, treecreepers, pardalotes, ducks and swallows. It may be purchased online at http://www.gould.edu.au/.
Alternatively, a Google search on “nest boxes” will reveal a number of sites describing nest boxes, with some for example, http://www.gardenexpress.com.au, selling nest boxes for various birds and mammals online.
A free-roaming cat is not compatible with having birds. A purpose-built back yard cat run allows room for cats to exercise, while protecting native birds in the rest of the garden. While dogs have the potential to do some damage to native wildlife visiting a garden, they are generally not the instinctive inveterate hunters that cats are.
Even if you choose not to have a free-roaming cat, there are almost certainly such cats in the neighbourhood. Any yard is likely to be taken over as part of the territory of at least one of these cats. One way to prevent this is to have a dog.