Malware, being a pretty new term has many different definitions. Although, I use the term to mean any malicious software on a computer (this seems reasonably consistent with much of the computing world). This (to me) includes three main categories spyware, adware, and viruses.
Here's a quick rundown of each of those terms:
Virus - this is a program that is set upon a computer with no intent other than to damage the computer, spread itself, and/or take control of the computer. Viruses can be either trojan viruses (which attach themselves to other, seemingly benign files) or worms (which spread themselves like biological viruses (hopping along from host to host in whatever way they're designed to). I hesitate to even use the word "virus" much anymore because people seem to associate the term with any malware, including adware and spyware. Viruses are the "worst" kind of malware. There is no justification for their existence.
Adware - Adware is pretty simple. It's software designed to advertise. Sometimes viruses are used to spread adware (as with some versions of Conficker). Sometimes adware is included in "free" programs as a way for the publisher or developer to make money. This is generally considered to be a bit underhanded (because sometimes they are less than straightforward about what you're getting in to). Adware is usually the source of "out of the blue" popups (that you get when you're not actually surfing the web). It works a bit like Spam. The intent is to hit as many people with ads as possible in the hopes that if 1 in 10,000 people actually responds, they still make a profit.
Spyware - Spyware is designed to "observe and report." It sits on your computer (often without making any sign of its existence) and watches what you do. This could be as much as recording every mouse movement and keystroke or as little as just checking what websites you visit or even how often you use a certain program. It then reports this data back to its owner.
There are other kinds of malware (such as "ransomware" -- a virus/adware hybrid that encrypts or locks your data until you pay the creator for its release). But those categories can pretty much encompass all the different stuff out there.
As for what makes something malware. Well, it's sometimes the intent in which it's created. Or sometimes the effect. But probably the biggest determination of whether something's malware is if it's deceitful. If the average user doesn't realize they're installing it, then it's malware. Even if it's bundled with something the user meant to install.
One such example of "gray area" malware is Warden . Warden is a program included with World of Warcraft (an extremely popular online game). It runs alongside World of Warcraft (WoW) and checks to see what other software is running at the same time. If the player is running anything that might help them cheat or gain an unfair advantage in the game, then Warden can be used to find out if they are and report back to Blizzard (the makers of WoW).
Another example is SecuROM . SecuROM is a gray area form of spyware/malware used (most notably) by EA. EA makes a number of extremely popular video games (including Spore, the Sims, and a host of sports games). SecuROM is designed to prevent unauthorized copying of the program it's attached to. In order to accomplish this, it can be set to do many things. One of those options is to prevent the game from being played if any disk image mounting software (such as Alcohol 120% or DamonTools) is installed. Both those tools are legal in themselves, but could possibly be used to assist in pirating software.
So to answer your question. It can sometimes be very hard to categorize something as malware or not. Both my "gray area" examples would seem to qualify as malware under my previous definition. However, they have not been determined to be illegal (to my knowledge) and many people are perfectly content with their existence and usage. It seems that malware is like pornography. In the words of a supreme court justice, "I can't really define it, but I know it when I see it."