I know it's been a little bit since you posted this, but I noticed that nobody responded to your thread yet. Web services has to do with computer systems exchanging information in a formalized manner. When you hear phrases like "We're integrating our software with a third party web service....", what they're really saying is that they're setting up the ability for your software and the third party's software to talk to each other for some purpose. Unfortunately, computers cannot communicate like you or I, so they depend on a set of formal rules for exchanging data. These formal rules are generally called an API.
There are two ways that web services are used: to get data from a third party and to push data to a third party. I don't know for sure about your situation, but from the description you gave, it sounds like your company was probably pushing data to the third party. I'm going to take some liberties here with the imagination to illustrate a point, so forgive me if this doesn't match what your organization actually does.
From a business perspective, your company has decided to use the third party to handle their newsletters. Probably, they're very good at sending newsletters, and to get the same quality in house would cost an arm and a leg. So they've entered into an agreement to use their services instead.
The problem comes in though every time you guys have a new customer. Someone has to pick up the phone or email and say "Hey Mike, this is Jim over at XYZ corporation, and we have 3 more people we need to add to our newsletter listing". Here's where web services become useful. A web service would allow you to set up a programmatic trigger so that every time a new customer registers your software, the customer is automatically signed up for the newsletter. Nobody has to talk to each other over the phone or email. The computers talk to one another and everything happens somewhat magically through this information exchange.
On a more technical level, almost every API has a formal set of syntax for how the information is passed back and forth. To give you a real world example, here's the documentation for a particular method of Twitter's API:
This method returns data to you about who is following the specified user. You can see from the documentation that you need to provide either a screen_name or user_id value when you send your request for data. Once your request has been processed, it will send you back data containing information about the people following the specified user id (see the example section at the bottom).
Every web service works differently, they use different syntax and rules for communicating. If you wanted to integrate with a particular web service (Facebook, Twitter, etc), you would review the documentation for that service and start writing code from there.
I hope this brief primer was useful to you. Have a good day!