"Is it fair to assume there is free software that may not be listed in the
FSF Free Software Directory?"
Yes - Not only fair, but likely.
"Is it all about a piece of software having a free license?"
Not necessarily, although that is one important thing. (I'm thinking of the
freely-licensed blobs in the kernel named Linux, for example - Although they
have a free license if you check the Free Software Definition, availability
of source code is a prerequisite. So if there is no source code then it is
automatically non-free, regardless of what the license might say.)
Other ways that freedom problems can arise are if a program is dependent on a
non-free program, either in order to use the program or compile it. (This is
also mentioned in the Free Software Definition.)
Start with reading Mr. Banana's links. It's a good place to get up to speed.
Then, deeper and more involved questions can be had.
