Libraries are files written in C or C++ (.c, .cpp) which provide your sketches with extra functionality (e.g. the ability to control an LED matrix, or read an encoder, etc.). They were introduced in Arduino 0004.
To use an existing library in a sketch simply go to the Sketch menu, choose "Import Library", and pick from the libraries available. This will insert an #include statement at the top of the sketch for each header (.h) file in the library's folder. These statements make the public functions and constants defined by the library available to your sketch. They also signal the Arduino environment to link that library's code with your sketch when it is compiled or uploaded.
To install your own library, create a folder inside ARDUINO/hardware/libraries with the name of your library. The folder should contain a C or C++ file with your code and a header file with your function and variable declarations. It will then appear in the Sketch | Import Library menu in the Arduino IDE.
Because libraries are uploaded to the board with your sketch, they increase the amount of space used by the ATmega8 on the board. See the FAQ for an explanation of various memory limitations and tips on reducing program size. If a sketch no longer needs a library, simply delete its #include statements from the top of your code. This will stop the Arduino IDE from linking the library with your sketch and decrease the amount of space used on the Arduino board.
To get started writing libraries, download this test library. It should provide a basic template for creating a new library. After you've made changes to your library, in order to get it to recompile, you will have to delete the .o file generated in the library's directory.