The basis of proxy data is to use the climatic information stored in geological data to understand climate changes in the past.  As no instruments were available to take readings of the climate, paleoclimatologists use the information stored in geological materials to determine the climate at a given time.
 
Proxy data is derived from several sources.  Pretty much any natural phenomena that changes with atmospheric conditions can be used as proxy data.  Examples of proxy data include:

1. Tree rings - since trees produce one ring per year, the widths, density, and isotopic composition reflect variations in climate.

2. Fossil pollen - each plant produces distinct pollen grains.  These shapes are used to identify what types of plants were growing at the time the sediment was deposited.  Assumptions about the climate can then be made from the types of plants found in each layer of sediment.

3. Ocean sediments - ocean sediments are made up of materials that were produced in the ocean or washed into the ocean from nearby land.  The fossils and chemicals found in the drilled cores of sediment are used to interpret past climate.

4. Coral - corals are hard skeletons that are composed of calcium carbonate, a mineral extracted from seawater.  The oxygen, isotopes of oxygen, and trace minerals can be used to determine the water temperature at the time the coral grew.  Using the temperature, scientists can then recreate the climate at the time the coral was alive.

5. Ice cores- located high in the mountains and deep in polar ice caps, these cores are composed of dust and isotopes of oxygen that can be used to understand the past climate.

Other methods include crop yields, harvest dates, glacier movements, insect remains, marine micro fauna and isotope measurements.

Strengths:  Proxy data provides a way to determine climate, as instruments were not available for measurements.  Natural systems are dependent on climate and as such assessments can be made.  The best hope for reconstructing the climate of the last five millennia are tree rings, pollen deposits from lakes, and ice cores as the dating is precise on an annual basis.  Used in conjunction with historical data and instrument data, if available, proxy data can give an accurate picture.

Weaknesses: Ocean sediments are typically hard to date.  Ice cores may be missing layers.  Glacial deposits are highly episodic in nature.  Some systems vary exactly with the climate while other systems may lag behind the climate by as much as centuries.  The data may not be consistent throughout the sample.  Data collection and analysis is a delicate operation and may not always be preformed perfectly.   What was true in the past may not be true in the future.    Materials needed for analysis may not always be found in the quantities needed.

 http://www.geo.vu.nl/~renh/ngshansabs.html

 http://www.ngdc.noaa.gov/paleo/primer_proxy.html

 http://www.ace.mmu.ac.uk/Resources/gcc/3-3.html