Getters and setters are often criticized as being not proper OO. On the other hand, most OO code I've seen has extensive getters and setters.
When are getters and setters justified? Do you try to avoid using them? Are they overused in general?
If your favorite language has properties (mine does) then such things are also considered getters and setters for this question. They are the same thing from an OO methodology perspective. They just have nicer syntax.
Sources for Getter/Setter Criticism (some taken from comments to give them better visibility):

http://www.javaworld.com/javaworld/jw-09-2003/jw-0905-toolbox.html
http://typicalprogrammer.com/?p=23
http://c2.com/cgi/wiki?AccessorsAreEvil
http://www.darronschall.com/weblog/2005/03/no-brain-getter-and-setters.cfm
http://www.adam-bien.com/roller/abien/entry/encapsulation_violation_with_getters_and
http://www.yegor256.com/2014/09/16/getters-and-setters-are-evil.html

To state the criticism simply: Getters and Setters allow you to manipulate the internal state of objects from outside of the object. This violates encapsulation. Only the object itself should care about its internal state.
And an example
Procedural version of code:
struct Fridge
{
    int cheese;
}

void go_shopping(Fridge fridge)
{
     fridge.cheese += 5;
}

Mutator version of code:
class Fridge
{
     int cheese;
      
     void set_cheese(int _cheese) { cheese = _cheese; }
     int get_cheese() { return cheese; }
 }

void go_shopping(Fridge fridge)
{
     fridge.set_cheese(fridge.get_cheese() + 5);        
}

The getters and setters made the code much more complicated without affording proper encapsulation. Because the internal state is accessible to other objects we don't gain a whole lot by adding these getters and setters.
The question has been previously discussed on Stack Overflow:

https://stackoverflow.com/questions/565095/java-are-getters-and-setters-evil
https://stackoverflow.com/questions/996179


Having getters and setters does not in itself break encapsulation.  What does break encapsulation is automatically adding a getter and a setter for every data member (every field, in java lingo), without giving it any thought. While this is better than making all data members public, it is only a small step away.

The point of encapsulation is not that you should not be able to know
or to change the object's state from outside the object, but that you
should have a reasonable policy for doing it. 


Some data members may be entirely internal to the object, and should
have neither getters nor setters.
Some data members should be read-only, so they may need getters but
not setters. 
Some data members may need to be kept consistent with each other. In
such a case you would not provide a setter for each one, but a single
method for setting them at the same time, so that you can check the
values for consistency.
Some data members may only need to be changed in a certain way, such
as incremented or decremented by a fixed amount. In this case, you
would provide an increment() and/or decrement() method, rather
than a setter.
Yet others may actually need to be read-write, and would have both a getter
and a setter.


Consider an example of a class Person.  Let's say a person has a name, a social security number, and an age.  Let's say that we do not allow people to ever change their names or social security numbers.  However, the person's age should be incremented by 1 every year.  In this case, you would provide a constructor that would initialize the name and the SSN to the given values, and which would initialize the age to 0.  You would also provide a method incrementAge(), which would increase the age by 1.  You would also provide getters for all three.  No setters are required in this case.

In this design you allow the state of the object to be inspected from outside the class, and you allow it to be changed from outside the class.  However, you do not allow the state to be changed arbitrarily.  There is a policy, which effectively states that the name and the SSN cannot be changed at all, and that the age can be incremented by 1 year at a time.  

Now let's say a person also has a salary.  And people can change jobs at will, which means their salary will also change.  To model this situation we have no other way but to provide a setSalary() method!  Allowing the salary to be changed at will is a perfectly reasonable policy in this case.  

By the way, in your example, I would give the class Fridge the putCheese() and takeCheese() methods, instead of get_cheese() and set_cheese().  Then you would still have encapsulation.



public class Fridge {
  private List objects;
  private Date warranty;

  /** How the warranty is stored internally is a detail. */
  public Fridge( Date warranty ) {
    // The Fridge can set its internal warranty, but it is not re-exposed.
    setWarranty( warranty );
  }

  /** Doesn't expose how the fridge knows it is empty. */
  public boolean isEmpty() {
    return getObjects().isEmpty();
  }

  /** When the fridge has no more room... */
  public boolean isFull() {
  }

  /** Answers whether the given object will fit. */
  public boolean canStore( Object o ) {
    boolean result = false;

    // Clients may not ask how much room remains in the fridge.
    if( o instanceof PhysicalObject ) {
      PhysicalObject po = (PhysicalObject)o;

      // How the fridge determines its remaining usable volume is a detail.
      // How a physical object determines whether it fits within a specified
      // volume is also a detail.
      result = po.isEnclosedBy( getUsableVolume() );
    }

     return result;
  }

  /** Doesn't expose how the fridge knows its warranty has expired. */
  public boolean isPastWarranty() {
    return getWarranty().before( new Date() );
  }

  /** Doesn't expose how objects are stored in the fridge. */
  public synchronized void store( Object o ) {
    validateExpiration( o );

    // Can the object fit?
    if( canStore( o ) ) {
      getObjects().add( o );
    }
    else {
      throw FridgeFullException( o );
    }
  }

  /** Doesn't expose how objects are removed from the fridge. */
  public synchronized void remove( Object o ) {
    if( !getObjects().contains( o ) ) {
      throw new ObjectNotFoundException( o );
    }

    getObjects().remove( o );

    validateExpiration( o );
  }

  /** Lazily initialized list, an implementation detail. */
  private synchronized List getObjects() {
    if( this.list == null ) { this.list = new List(); }
    return this.list;
  }

  /** How object expiration is determined is also a detail. */
  private void validateExpiration( Object o ) {
    // Objects can answer whether they have gone past a given
    // expiration date. How each object "knows" it has expired
    // is a detail. The Fridge might use a scanner and
    // items might have embedded RFID chips. It's a detail hidden
    // by proper encapsulation.
    if( o implements Expires && ((Expires)o).expiresBefore( today ) ) {
      throw new ExpiredObjectException( o );
    }
  }

  /** This creates a copy of the warranty for immutability purposes. */
  private void setWarranty( Date warranty ) {
    assert warranty != null;
    this.warranty = new Date( warranty.getTime() )
  }
}

