First, what do you mean by "ran a software scan"? And why would a "software security audit" have anything to do with whether the software is legal?
Are all of these “free” in terms of license use?
Anything you install from the Software Center on a default installation (that is, you haven't done anything to modify where Software Center looks for software), is legal to use, yes (in Ubuntu 12.04 and 12.10, some software isn't necessarily monetarily free, but those are labelled as such). The same goes for Yum, Zypper, and the other package managers for the other distributions, since they have to comply with certain standards (either legal, or self-imposed) for distributing software bundled with the operating system or turned on by default in the package manager.
Where things get more hairy is when you start downloading software from the Internet. In that case, it's just like any other platform. Not only is the licensing going to depend on the software, but its legality is going to depend on where you get it. For example, a bootleg copy of Halo is still a bootlegged copy of Halo, but getting the latest version of Gimp or Chrome from their respective websites is perfectly legal, as is installing a legitimate copy of Halo.
Are all distributions of linux licensed for free to use?
Technically speaking, no, because it's likely there are versions of Linux out there that are under more restrictive licenses. This is the nature of the ubiquity that Linux actually enjoys (which most people don't realize), and the wording of the common licenses (which often allow you to build off an open source item and redistribute your new work under a more restrictive license). It's very likely that the version of Linux used as a base for Motorola's cable modems, or Cisco's routers, are under a more restrictive license model, making it not legally free to use.
That said, for typical desktop purposes, the Linux distributions you're likely to find and use will be free to use, in both the "free as in freedom" and "free as in beer" senses. However, if you have any doubts, you can always look up what license the distribution is released under and read the terms of the license itself. Most are released under the GNU GPL (or LGPL), MIT, Creative Commons, or Apache licenses, or some variation thereof, so those would be a good place to start.
Additionally, the Linux kernel itself (the core that all Linux distributions are built from; it's what makes them all "Linux"), is open source and free to use. Specifically, it's distributed under the GNU GPL version 2.
If I want to run a software security audit on my linux machines, do I need to bother or is there a legal document stating that all apps and software on this linux machine is legal to use?
You're not going to find a single legal document stating what you want. However, as I mentioned earlier, most Open Source software is licensed under one of the aforementioned licenses. Feel free to read them, but generally speaking, they all allow you to use them for personal and commercial use. Additionally, any software title will come with either a EULA (which usually means it's closed sourced or otherwise restricted) and/or a license, either of which will state the terms under which you're allowed to use the software. When in doubt, read the license that ships with the title in question.
If you're planning on letting other people use your computer(s) and allow them to install software (especially if you're looking for enterprise/business use), then it would still be a good idea to occasionally run audits to ensure that all of the software installed is legal. If you're just using it for home purposes, then there's not really any need.
For more information on open source software in general, you might want to check out the Free Software Foundation.