Tip of the day: Use the internet to take advantage of the public domain.
Foreign Service Institute Language Courses: Designed and written by the US government but with no copyright protection. You can download the texts (PDF format) and audio files (mp3s) for free. Not all languages are available for download as the site depends on user contributions and it takes a long time to scan the books and digitize the audio cassettes. Best for beginners because there is a lot of repetition and drills.
The following languages are available: Amharic, Arabic (Levantine & Saudi), Bulgarian (text only), Cambodian, Cantonese, Chinese, Chinyanja (link currently broken), Finnish (audio only), French, German, Greek, Hausa (text only, but see below), Hindi (text only), Hebrew, Hungarian, Igbo, Italian (text only), Kituba (text only), Korean, Lao, Luganda (text only), Moré, Portuguese, Romanian (text only), Russian (text only), Spanish, Sinhala (text only), Swahili, Swedish, Thai, Turkish, Twi, Vietnamese, and Yoruba (text only).
If you plan on downloading several files, try the DownThemAll add-on with Firefox. Instead of right clicking and downloading each file individually, you can download them all (hence the name) in one click. Plus it makes downloading much, much faster.
Also check the Forum to see if more materials are available (such as .torrents), but have not been uploaded to the site yet. For example, Serbo-Croatian, Igbo and Hausa PDFs and mp3s can be downloaded as torrents.
Project Gutenberg: Electronic version of books whose copyright have expired in the US (essentially all books published before 1923 and some published before 1964). Many classic books in several languages are available.
Children’s Library: Famous children’s stories in many languages (again, with expired copyrights), some with audio so you can listen while you read.
Thanks to the public domain, sometimes you don’t need to spend any money on language resources. If you do choose to buy language books, beware of certain publishers who copy the FSI courses and publish them for profit. For example, Barron’s Mastering Hebrew is the FSI course, which you can download for free!
P.S. The Defense Language Institute also produced language materials and they are available as micro-fiched PDF documents through the ERIC database. Unfortunately, there is no audio available and they’re a bit more cumbersome to download (you must do them one by one). The following languages can be found by searching for Defense Language Institute + the language + Full Text only: Albanian, Arabic, Mandarin Chinese, Czech, French, German, Haitian Creole, Indonesian, Japanese, Korean (advanced), Malay (intermediate advanced), Persian, Polish, Portuguese, Russian, Spanish, Thai.
P.S.S Although ielanguages.com is not technically in the public domain, all of the language learning resources are free.
MOOCs for Learning Languages
Free Peace Corps Language Learning Materials: Over 100 Languages Available
iTunes U Materials and MOOCs Available in Languages Other than English
Free Children's Books Apps in Foreign Languages
Open Lectures, Course Materials, MOOCs, iTunes U: The Internet is for Learning
Comparative and Multilingual Books for Learning Languages Simultaneously [UPDATED OCT 2014]