An encyclopedia is a publication which seeks to catalogue human knowledge; it is not the same thing as a dictionary because each article is linked to others.
The word encyclopedia comes from the Greek enkyklios paideia by way of French encyclopédie. Paideia means education and enkyklios means "in a circle".
The modern sense of "reference work arranged alphabetically" takes away from what an encyclopedia really is. A dictionary is also an alphabetically-arranged reference work. The purpose of an encyclopedia is to arrange human knowledge in a circle. In an encyclopedia the footnotes of an article reference to other (not so) related articles of the encyclopedia, connecting all the articles inside a system.
An encyclopedia is the application of the philosophy that everything is connected. One entry is informative, but it is by how it relates to the rest of the body of human knowledge that it takes on its full meaning. It is not just the facts and ideas that matter but the relations between them : it is not the what that matters but the why. You look up something in a dictionary; in an encyclopedia you can start anywhere and go on forever, at least theoretically. Ambitious French philosopher Auguste Comte declared that an encyclopedia should contain the entire body of human knowledge, notably by unifying all sciences; however an encyclopedia is not the sum of human knowledge. An encyclopedia is exactly what the word means : human knowledge organized in a system, in a cycle.
Interesting Tidbits
If someone says "the encyclopedia" it's likely they're referring to the Encylopédie ou Dictionnaire raisonné des Sciences, des Arts, et des Métiers, written between 1751 and 1765 in France and edited by Denis Diderot and Jean Le Rond d'Alembert. Note how the encyclopedia is also called a "dictionaire raisonné", reasoned dictionary, putting the emphasis not on the information included but on the reasoning, on how the information is organized.
The cross-referencing of articles make encyclopedias the first real hypertexts. Therefore, thanks to its hypertextual user-created content the World Wide Web is the world's largest encyclopedia. However, thanks to the nifty idea that is softlinking, E2 might be the most efficient one, and the closest to the original idea that exists out there. The ubiquity of hypertext has made pretty much every on-line dictionary or reference archive a wannabee encyclopedia.
Note the irony of the fact that most encyclopedias are hosted on, and therefore a part of the bigger encyclopedia that is the WWW. Which makes sense; after all, if an encyclopedia is to compile all of humanity's knowledge, wouldn't that include the other, smaller ones?
By encyclopedia, people often refer to one of the earliest, and certainly the most famous encyclopedia, which was published in France in the 18th century, and is noded under L'Encyclopédie.
Thanks Cletus the Foetus for pointing out my careless logic.