In general, SpyWare is any technology that aids in gathering information about a person or organization without their knowledge in order to build profiles. The collecting party is usually of the advertiser variety. SpyWare usually comes in the form of software included with "free downloads" from the Web, where the licence agreement (which most users accept without reading) may mention that information about your habits will be transmitted back to the company. It may however also come as the payload of a Virus, or just by clicking on a button in some pop-up ad window. SpyWare is cause for public concern about privacy on the InterNet.
Data collection programs that are installed with the user's knowledge are not, properly speaking, SpyWare, if the user fully understands what data is being collected and with whom it is being shared.
This type of software generally only affects Windows systems, where it will often lead to greatly degraded system stability. If you're running Linux or FreeBSD you're probably never going to be bothered by large pop-up purple monkeys or yellow links.
Examples include:
Most such SpyWare can be removed by Ad-aware or and SpyBot - Search&Destroy, both of which work well and can be updated via InterNet. For best results, use both of them. In some cases the SpyWare will try to remove Ad-aware and/or try to prevent Lavasoft's download site from resolving, so you might have to download it via an uninfected computer.
Many other programs claim to be SpyWare removers are SpyWare themselves.
Note that most removal tools will detect a (safely removable) cookie from the Alexia SpyWare program even on a clean install of Windows, as Microsoft includes it with the default install and updates it every time you use !WindowsUpdate?.
There is also a category of "real" software that "phones home" in ways that (perhaps) it shouldn't.
RealPlayer and WindowsMediaPlayer are notorious for this, though you can nowadays shut up most of their attempts if you dig through the configuration deep enough. This wasn't always the case, though, and even now most users will just use the defaults, not knowing any better.
If you use the "pagerank" feature of Google's toolbar, it will report every URL you visit back to Google. Officially it's required behaviour for Google to tell you what the pagerank is; unofficially that's a vast amount of information and it's not clear what else Google uses it for. Most people trust them, because they have a history of not being evil.
One page links to SpyWare: