BMI is an actuarial table, and while grossly inaccurate for people with muscular or other types of extreme builds, for a general guideline it will work, especially if you are mainly targeting fat loss. So, take a look at the BMI scale, pick out a reasonable weight goal and aim for that in the beginning.
To start, I would not only design an exercise program, but I would also design a lifestyle nutrition plan. I don't say diet, as diet implies a short term change. There are two main components to fitness, one is exercise and the other is what you eat. Only if you really pay attention to both, can you really be successful at losing the weight and getting fitter.
Get a physical, start with moderate level, low impact exercise such as cycling, swimming, walking, and basic weights. Get your weight into a manageable level, and along the way find out what kind of exercise you like, and design your exercise plan around that activity. If you hate weightlifting, you won't do it for long, for example.
Bodyfat can be measured by a Tanita type scale, bodyfat calipers, circumference measurement, and advanced methods such as underwater displacement weighing and DEXA scans. The last two are the most accurate, then calipers, then the rest. A Tanita scale, while possibly very inaccurate, does at least give a general trend. One of your best aids will be the mirror and your clothing.