What kind of waste is a battery?
Battery disposal 101

Waste batteries have different disposal requirements depending on the size and chemistry -- disposing of them with common waste is generally a mistake, but this mistake is more tolerable for some chemistries than others.  For bare coin/cylindrical cells or PP3 (9V) batteries of all chemistries though, a piece of electrical tape should be placed over the + electrode, or both electrodes for that matter, before disposing of the battery -- this prevents shorts in waste battery containers, which can lead to fires.  Short-circuit prevention is also important for lead-acid starting and marine deep-cycle batteries -- most small sealed-lead batteries and manufactured packs have connector/contact designs resistant to accidental shorts, though.

TL;DR:

Safe to dispose of in non-biodegradable household waste (but can be recycled with other batteries):


Alkaline
Carbon Zinc
Lithium primary "AA" and "AAA" (LiFeS2)
Lithium coin "CR" (LiMnO2)
Zinc-Air


Should be recycled in a battery recycling stream (i.e. they won't do anything nasty to the landfill but would be silly to throw away or pose environmental hazards in large quantities):


NiMH
Silver Oxide (AgO)


Must be recycled in a dedicated battery recycling stream!:


Lead-Acid (flooded and sealed/AGM)
Nickel Cadmium (NiCd)
Mercury primary
Exotic lithium primary (LiCF, LiSOCl2)
Lithium Ion/Polymer


Common (cylindrical/prismatic) primary chemistries (CZn, Alkaline, LiFeS2)

This covers AA, AAA, AAAA, C, D, and PP3 (9V) cells/batteries used in general applications.  A few rarer types such as N and A23 also fall here, as well as some photo batteries and coin cells that use alkaline chemistries.

These can be disposed of with other batteries in a battery recycling stream, or as general household waste (i.e. non-compostable/non-biodegradable) in most areas -- reputable primary cells of these types no longer contain mercury or other things that make them hazardous to dispose of.

Coin cell/watch battery primary chemistries (ZnAir, AgO, LiMnO2)

These chemistries are primarily found for coin cells and "watch" or "hearing aid" batteries.  Note that older or more oddball coin-type cells may contain more exotic chemistries such as Hg or LiCFx that must be disposed of in a dedicated battery recycling stream.

Silver oxide batteries should be disposed of in a battery recycling stream (as they contain valuable silver that can be recovered -- old ones had mercury in them, but the mercury containing types are no longer made by reputable manufacturers).  Common consumer lithium coin cells of the "CR" chemistry type (LiMnO2) and zinc-air cells can be disposed of either in a battery recycling stream or as general waste (again, non-biodegradable) in most areas.

Nickel based secondary chemistries (NiCd, NiMH)

Nickel based secondary chemistries include the obsolete NiCd (Nickel Cadmium) cells and more modern NiMH (Nickel Metal Hydride) cells.  The former are most commonly seen in old rechargeable battery packs used for power tools, portable equipment, and other miscellaneous applications, while the latter are both seen in smaller pack applications and as bare cells.  There are also flooded and recombinant NiCds used in some large format applications -- these are long-lived and not seen in the consumer world, so won't be discussed further here.

In the case of NiCd cells and packs, they must be recycled in a battery recycling stream due to the toxic cadmium in them.  NiMH batteries don't contain particularly toxic materials, but should be recycled as well to recover the nickel content, and can be problematic when disposed of in quantity.

Lead Acid secondary (sealed and flooded)

Lead Acid batteries must be recycled, for obvious reasons -- besides, they are simple and highly economic to recycle.  Automotive battery recycling has been the primary driver of battery recycling for over a century now, and you can even get a small return payment for turning in dead starting (car, motorcycle, boat, or small-aircraft) or deep-cycle lead-acid batteries in some locales.  Small-form sealed-lead cells don't have quite this many incentives, but should definitely be recycled as well!

Lithium Ion Secondary (LiIon/LiPo)

Lithium-ion secondary cells must be recycled, especially in larger form factors and quantities.  This is partly for environmental reasons and partly because household waste processing can mechanically damage (crush) cells, which has the potential to lead to a smoking trash truck or trash compactor/chute fire.  They also should not be mixed with lead-acid recycling streams -- most locations that accept nickel-based chemistries can deal with lithium-ion as well, though.

Exotics and miscellaneous chemistries

If you run into exotic or obsolete chemistries/configurations (flooded nickel cadmium or nickel iron, mercury primary, lithium metal secondary, lithium metal primary other than CR/LiMnO2 or FR/LiFeS2), send them to a dedicated battery recycler who deals with commercial/industrial batteries and be certain to include as much information about the chemistry as possible.  Also make sure to insulate the terminals!

Nickel zinc secondary and nickel oxyhydroxide primary cells can be recycled in a nickel battery stream, but do not pose undue disposal hazards in small quantities when disposed of in household non-biodegradable waste.  Water-activated batteries such as those found in radiosondes are intended to be disposed of as non-biodegradable household waste.