What are you using now to record the services (camcorder make/model)?
Depending on that you are doing now, a simple program like Roxio's Easy VHS to DVD will let you capture video and then burn DVDs. CDs won't hold enough info unless your sessions are short or of lower video quality.
Here is a link for the product (includes the needed capture device):
Windows comes with SOUND RECORDER. Any laptop or PC with win7 will work, sound quality will be how well you get eh sound into the PC. Are you already amplified during the service? YES -- cool, you can patch from the amp that drives the speakers directly into the PC sound card thru a monitor out. NO --Put your money into the microphone. Go to a store that sell used music equipment. Tell them what you want. If you walk around while talking get a wireless mic that hangs at your neck HIGH up. Then practice recording to see how far your head can turn before you lose sound. If you stand at a podium tell the music store. They can set you up. Bands need exactly this equipment and have the same need to record. If any of your church members are in a band they will know how to set this up.
Typically the best way to record is to keep the recoding running then to edit afterwards. You can divide the service up into tracks with any of the many many available audio edit software. Once edited, you have the master for your CD.
Once you have the service master recorded see how many copies you need. Burning bank CDs is easy but tedious. 10-20 you can do yourself. I would not attempt to burn 100 a week. Places like this one I found at random on google and have never used, specialize in burning CDs for you. http://www.bisondisc.com/ Go this route rather than sitting there swapping CDs every 5 mins for hours.