The MechanicA permanent that has Indestructible cannot be destroyed, and cannot be killed as a result of lethal damage. Similarly any Artifact, Land or Enchantment with indestructible is immune to destroy effects.
Indestrucible recently was changed to a keyword, meaning that cards which say "[This Card] is indestructible" are given errata which says "[This Card] has indestructible." This is relevant only a few cases. For instance, with this new ruling, a card such as Ovinize which removes all abilities. Previously, a card that was indestructible would still not be able to be destroyed. However, now the card loses the "indestructible" key word and can be destroyed through normal means. Also, if an effect would make creatures you control indestructible (such as Boros Charm) any creature you play after that effect resolves will not get indestructible.
An indestructible creature is complicated. Combat damage does not kill it. Any card that deals damage to it, like Pyroclasm or Tendrils of Corruption, will not kill it. The only way to kill an indestructible creature is by giving a toughness of 0 or less. The most obvious way to do this is by giving it -1/-1 or -0/-1. Infect creatures are a good way to do this, as they give creatures -1/-1 counters. Other cards like Infest can also kill indestructible creatures if they have a toughness of 2 or less.
Suppose a player has a Darksteel Myr on the battlefield, which is a 0/1 indestructible creature. His or her opponent has a 4/4 creature down like Rhox Brute. He or she attacks with it. If the player blocks with his or her Darksteel Myr, nothing will happen. The Myr will deal no damage to the Rhox Brute, and the Rhox Brute will not be able to kill the indestructible Myr. The opponent then casts a Terminate and targets my Myr. Since the Myr is indestructible, the spell will do nothing. Then the opponent casts Infest. Since Infest does not "destroy", and Infest does not deal damage, the Myr will die because its toughness is less than 0.
Other ways to deal with indestructible permanents.
Permanents that have indestructible can be dealt with in other ways that do not destroy them. You may exile them, which removes them from the game, such as with the card Unmake . They may be returned to their owner's hand. They can be sent to the top or bottom of an opponent's library, or shuffled back into an opponent's library depending upon the cards that you use. You can of course use Auras such as Arrest to prevent indestructible creatures from attacking, blocking, or using their activated abilities, or tap them and keep them tapped with other cards like Sleep or Glimmerdust Nap. You may also cause your opponent to sacrifice their indestructible permanents with cards like Diabolic Edict or an Eldrazi's Annihilator ability. Indestructible cards may also be countered.