One big thing I've learnt is to design classes from the outside in. Design the interface before you even start thinking about the implementation. This will make the class much, much more intuitive for your users (those using the class) than writing the underlying algorithms and building up the class, and writing new public member functions as they are needed.
OO is usually "defined" in terms of four basic requirements:
Abstraction means you're able to separate an objects externally visible behavior from its implementation.
Encapsulation means being able to hide the details of the implementation of an object (so closely related to abstraction that some authors treat them as one, leaving only three major requirements).
Modularity means being able to package abstractions into discrete units.
Hierarchy is a ranking or ordering of abstractions -- an ability to define the relationship between one abstraction and another.
I, for one, would consider a language object oriented if it supports these four major requirements. Supports, however, goes a bit beyond "allows" or "tolerates".
C, for example, provides enough flexibility that you can simulate each of these reasonably well. C, however, provides only a little support for abstraction or modularity, and none at all for encapsulation or hierarchy -- you can do these things if you want to badly enough, but the language doesn't really provide any direct support for them.
C++, for an obvious comparison does provide direct support for each of these requirements. Just for example, encapsulation is directly supported by making class members private and/or protected and hierarchies are supported via class inheritance.
That's still not what would normally be called a "pure" object oriented language though. In a pure OO language (e.g., Smalltalk), you not only get support for hierarchy, but you get a pre-defined hierarchy of types, and you have to define the relationship of any new type to some existing type in that hierarchy (i.e., all your code most be in classes, and each class must derive from some existing one).
Although classes and inheritance are both common to many implementations of object orientation, neither is really necessary to it. Just for example, Self and JavaScript both use exemplar-based hierarchies. Instead of a hierarchy of classes, with each object an instance of a class, these just use a hierarchy of objects, with each based on some other object, but modified to some arbitrary degree.
Best Answer
Abstraction and Encapsulation are really the only things required for something to be object- oriented.
Inheritance and polymorphism are strategies to take advantage of NOT "reinventing the wheel" which is a benefit to using OO designs.
The base idea behind OO design is to get a large amount of programmers to work together on project X without incurring massive communication overhead, and breaking a project down into objects with defined communication between them is an elegant solution.