Help Restore as New Battery issues

Long story short my battery has gone south on my new 4s. I drive 75 miles to the Apple store to get it fixed and the guy says the issue is a software problem and he "fixes" it . Get home and connect to the computer and when it prompts me to restore i must have said yes to restore as a backup. Problem not resolved back to no battery. call apple and they tell me i should have backed upped as "new". Okay so i get on Itunes and i can't figure out how to do this. HELP. How do i do this please.