There are 2 general approaches for design when doing something that is vaguely object oriented. One is to decompose you data into structures, figure out the entity-relationships (often with a diagram) and then finally decide which operations should live on which object. When I first started out in the 80's this was pretty much "the way". You would frequently write descriptions of the domain, circle all of your nouns and underline your verbs. Then you would make data structures with the nouns and make methods with the verbs.

A lot of this stuff came out of the Simula branch of OOP. It's the kind of stuff that C++, Java, C#, etc was modelled around. Objects are an encapsulation of data along with their operations.

The other way to go is more where the Smalltalk guys went. In this branch of OOP, what's important are the messages. Data is abstracted out and your goal is to refer to it as little as possible. Instead messages are passed around between objects and the objects are responsible for dealing with the messy business of handling the actual data. When you are designing you look for the message flow and then build objects that handle the messages.

When one says "Start writing an interface, not a class", I think what is meant is that you should concentrate on the messages that the objects need to react to, not the data within the classes. So you are designing a protocol, not an E-R diagram.

There are people who are adamant that only one of these two approaches will result in "good code". Often there is a considerable amount of derision for someone who believes in the opposite approach. The truth probably lies somewhere in between IMHO. There are advantages and disadvantages. When doing a data centric approach, it's very easy to understand the state that you are capturing. But it's also very easy to let the details of the data dominate and to create unnecessarily complex code dealing with that data. Often you end up with god objects and poor decomposition of behaviour. On the other hand, if you go for the protocol approach, often you get designs where the state is almost impossible to figure out and where you have "big bags of functions" because it is convenient. It is difficult to maintain the data abstractions and often the data details leak out, pretty much destroying your design.

Design is super difficult and requires a lot of experience of doing it. Different schools of thought and descriptions of approaches are helpful to a certain degree, but the best is to write a lot of code and get feedback from people with experience. My biggest piece of advice for people who are near the beginning of their career (i.e. first 10 years or so) is to try to work on an project (likely your own side project) for at least 5 to 10 years so that you can see it implode under its own weight. The biggest mistake I see developers make is assuming that things that appear to work for a year or two will continue to work as the code base ages. Especially I find people who have formulaic approaches to design often break the design badly in the long term (there are some 3 letter abbreviations that I could splash out if I wanted to pick a fight ;-) ) Unfortunately, these people rarely work on a project for more than a year or two, so you get what I call "drive by designings" -- just shoot it to pieces and drive on.