get up in your attic and seal up all penetrations, all phone lines, electric wires, pipes, and heating duct penetrations. use expanding foam. you may need to bridge the gaps using scrap wood if openings were cut sufficiently large
make sure your duct work is not losing air to the outside. go along them and pull back insulation at joints and apply a good foil backed duct tape to ALL joints.
add additional insulation to duct work if needed. In my house, some of it was coming lose. At a minimum, tape it all back into place.
when the above three are done (in the attic at least) blow in more insulation. Make sure your soffits are not blocked
make sure your attic door has a good seal and is insulated, make an insulated door if you don't already have one
buy programmable thermostats, then install them
if your basement/crawl space is not insulated, do so.
If your walls are in poor shape, you may want to look into removing the drywall/plaster and installing a Mooney Wall
for a higher R-Value
If you are going to replace your windows, get ones that do a better job at keeping sunlight out and heat/cool in.
If you are replacing your roof, consider going with a lighter colored shingle, the lighter the better, better yet, consider a non-asphalt based shingle, or steel roof... better than any of these, consider a thin-film-solar steel roof, like Marathon Solar Roofing
When doing your roof, consider adding overhangs for windows to keep sun out during the summer, but allow it in during the winter
Check the seal around your doors, odds are it's pretty old and could use replaced. Very easy to do, and prevents some major drafts
Seal up windows in the winter, use the plastic kits you can get almost anywhere to prevent leaks, and increase the insulation between you and the outdoors.
Grill out during the summer, or look into making a solar oven, or eat more salad... anything to avoid using your oven indoors!
I would suggest we break it down further into "summer tips" and "winter tips"