Mike Perry's answer covers much of the food and water aspect. There's also the perspective of shelter. Depending on what kind of birds you want to attract, planting trees and landscaping in a way that provides small birds with protection from predators encourages them to stick around when they've discovered that your yard is a good source of food. A retaining wall behind our house is built out of loosely stacked boulders (i.e. lots of cracks). The wrens (my best guess at identification) seem to really like this for nesting.
Do your gardening and landscaping with a minimum of chemicals and a consideration for the ecology of your yard. You want to reduce the possibility of causing a negative impact on the bird population, and some chemical applications have unintended consequences. E.g. some grub killers kill earthworms. Some birds eat worms (and grubs) -- if you kill off their food source, they're not going to come around anymore. Similarly some garden poisons may have
Similarly, if you want a variety of birds, you need to provide a variety of food sources and shelters. Just as you might have different kinds of bird feeder and seed mixes to accommodate different species, you should consider different habitat choices and preferred foods for the birds you are trying to attract.
If you have a larger property with lots of trees, you don't necessarily want to cut down dead or dying trees. These "snags" are habitat for woodpeckers and make good perches for predatory birds to scan the landscape. We had a massive turkey vulture perched on a snag behind the house earlier this summer. It was an incredible thing to watch it land and take off again. I've seen hawks come and go too.
Again if you have a larger yard, and live in an area where it wouldn't be politically incorrect to "let it go", you can plant (or let go) a section of your yard to "meadow". Part of our front lawn is heavily "infested" with daisies as weeds (purely volunteers, we didn't plant any seed there). Earlier this summer we decided to simply stop mowing since the daisies were coming up so thickly (along with some red clover). The birds seemed to like it some -- especially our guineas -- but I think we mowed it too soon after the flowers died back, and I'm not sure daisies really produce enough seed to be attractive to birds. If you wanted to try something similar, you could look for plant species that your local birds would like.
In that same vein, we've got a flower garden that was started with weeds pulled out of roadside ditches. These native weeds look nice (we didn't pick the ugly ones), are known to be hardy to the area, are familiar to the birds in the area, and have grown enough in three or four years that we can hack them back with a spade to keep them in check.
Lastly, if you really want to attract birds, plant some berries or fruit trees for yourself. In my experience, once you do this it's impossible to keep the birds away!