Public domain refers to information, data, textual or artistic work that is available to the public. In copyright terms, it means the information is freely available for copying and distribution. In broad terms, works that are not covered by copyright, patent or other form of legal protection are considered to be in the public domain and may be accessed, used, copied and distributed by anyone, with public domain status typically being due to the copyright/patent having expired (with patents lasting fewer years than copyright) or the copyright/patent holder having released it into the public domain intentionally, such as with the CC0 license from Creative Commons (see below). (Note that copyright is automatic in most countries in modern times, so a recent work can be assumed to be copyrighted even if there is no copyright notice (typically a © symbol and the publishing year) present).
Since copyright and patent laws vary from nation to nation, what is or is not public domain can be confusing. Most of the contents of Project Gutenberg, for example, are in the public domain in most countries; however, due to differences in copyright regulations across national borders, Gutenberg Australia, though related, has much material that is in the public domain in Australia that is still covered under United States copyright. (Remember to consult your local copyright authorities before loading up on George Orwell bootlegs.)
Much software, including many free software packages and virtually everything produced by the United States government (see ImageJ for one example, a high-quality image editing program written in Java), is public domain; however, most freely distributable software is copyrighted, usually under an open source license that asserts the creator's copyright while explicitly giving the user many, but not all, of the rights associated with public domain distribution.
Creative Commons, which mostly makes licenses that still use copyright but with less restrictions, has the CC0 public domain dedication for those who want to dedicate their work to the public domain without having to go through longer and more formal procedures. The dedication also provides a loose fallback license for when works that use it cannot be dedicated to the public domain.
Other legal meanings
In a broader sense, information or knowledge is "in the public domain" (as opposed to being unknown, a trade secret or whatever) if it is known to or available to the public at all, even if under copyright or other restrictions.