There's a lot of data to support exercise contributing to better physical health and mental health. A 2005 study from Brazil targeted the elderly, and states:
Comparing the groups after the study period, we found a significant
decrease in depressive and anxiety scores and an improvement in the
quality of life in the experimental group, but no significant changes
in the control group.
The Mayo clinic spells it out pretty clearly as well:
Research on anxiety, depression and exercise shows that the
psychological and physical benefits of exercise can also help reduce
anxiety and improve mood.
The links between anxiety, depression and exercise aren't entirely
clear — but working out and other forms of physical activity can
definitely ease symptoms of anxiety or depression and make you feel
better. Exercise may also help keep anxiety and depression from coming
back once you're feeling better.
An interesting concept is found in yet another study with positive correlation results between exercise and mental health (this time in breast cancer survivors):
Mild to moderate aerobic exercise may be of therapeutic value to
breast cancer survivors with respect to depressive and anxiety
symptoms but not to self-esteem. A physician's recommendation to
exercise appears to be an important factor in a patient's exercise
adherence.
Sticking With It
Every thing I've seen, and what I've referenced shows that there's a clear connection between physical fitness and positive mental health results. In that first study the subjects were exposed to ~30 minutes of aerobic activity for six months. In the latter study, it's noted that the power of a physician's recommendation was needed for the results, simply because of adherence.
So whether it's about body building results or keeping depression at bay, the deciding factor is consistency. An old running coach told me that training is like trying to fill up a bathtub one teaspoon at a time, with each day representing a teaspoon: there's no way to rush the process, and it's the cumulative impact over time that matters.
Exercise types
The data currently suggests that effective workouts you stick with are by far the deciding factor in impact. A "more effective" activity that you don't do like clockwork is as a result less effective.
I'm a huge advocate of strength training. Perhaps you can put another question together outlining your physical fitness goals and what you have to work with (gym membership, ice rink, you live in the woods, etc).