Both.
Find some way to incorporate some of the following lifts into your routine:
Squats, Deadlifts, Bench Press, Rows (dumbells), Military Press/Overhead Press, Pull Ups/Chin Ups
This may be a helpful routine for you. I do it when I'm trying to cut fat and maintain strength, but you might find it helpful too:
http://newbie-fitness.blogspot.com/2...ipped-5x5.html
Others can chime in with better advice than me, but you don't necessarily need anything fancy at your level. As Milkster noted, do some sort of routine that incorporates those lifts.
I'm not as good at figuring out what set/level of reps work for people, but I've always had the most success/least boredom doing a 5 x 5.
I know some of those lifts are unpleasant at first (and maybe will continue to be), but you need to include them. ESPECIALLY squats and deadlifts.
Hope that helped. Congratulations on taking the first steps. I'm glad you're at least paying attention to the diet.