What is public domain software?

Public domain software is software that is not copyrighted. If the source code is in the public domain, that is a special case of non-copylefted free software, which means that some copies or modified versions may not be free at all.
In some cases, an executable program can be in the public domain but the source code is not available. This is not free software, because free software requires accesibility of source code. Meanwhile, most free software is not in the public domain; it is copyrighted, and the copyright holders have legally given permission for everyone to use it in freedom, using a free software license.
Sometimes people use the term "public domain" in a loose fashion to mean "free" or "available gratis." However, "public domain" is a legal term and means, precisely, "not copyrighted". For clarity, the Free Software Foundation recommends using "public domain" for that meaning only, and using other terms to convey the other meanings.
Under the Berne Convention, which most countries have signed, anything written down is automatically copyrighted. This includes programs. Therefore, if you want a program you have written to be in the public domain, you must take some legal steps to disclaim the copyright on it; otherwise, the program is copyrighted.