It is always a herculean task to write automated regression tests for a legacy application. The questions vary from where to start, how much to automate and deciding on the best strategy for automation.
Responding to a thread started by Mark Levison on the Agile software testing group, Hubert Matthews suggested that the approach that he recommends is a risk based approach.
You can never test everything so you have to choose where you want to spend your time and money. Testing for me is primarily about information and risk and not about blanket coverage or completeness.