Para complementar, vou citar dois livros que acho excelentes:
Utilizando UML e Padrões - Craig Larman - esse livro diz que a habilidade mais importante para desenvolver sistemas orientados a objetos é saber atribuir responsabilidades às classes.
Padrões de Projeto - Gangue dos Quatro - é o primeiro livro de design patterns. Além disso fala sobre os princípios para um bom projeto de software. Um ponto interessante é que as a API’s do Java aplicam diversos padrões de projeto apresentados nesse livro, como por exemplo Adapter, Iterator e Observer.
Respondendo à pergunta, acho que o primeiro passo para programar orientado a objetos é entender a teoria e os princípios. Você pode aprender numa boa faculdade ou curso, ou com um bom livro. Em particular o livro do Craig Larman traz a teoria. Ensina sobre acoplamento, coesão, princípios para atribuir responsabilidades. Traz também bons exemplos.
O segundo passo é colocar em prática, fazer sistemas tentando aplicar os princípios. Fazer diagramas de classes e de sequência ou colaboração para avaliar as questões de acoplamento, coesão, controladores e responsabilidade por criar objetos, coisas assim. Esses diagramas podem até serem feitos à mão, mas acho que ajudam nessas questões. Depois de um tempo você percebe que os seus sistemas estão ficando mais orientados a objetos, que as classes têm responsabilidades bem claras e definidas, são coesas, não têm acoplamentos desnecessários ou em excesso. Que o seu sistema é fácil de entender e manter.
Aplicar padrões de projeto também é bom, porque são soluções já testadas e com eficiência comprovada. A questão é saber quando o padrão se aplica e se compensa utilizar.
Abaixo links para os livros:
http://www.submarino.com.br/produto/177684/livros/informatica/informatica/livro–padroes-de-projeto
http://www.submarino.com.br/produto/5638283/livros/informatica/metodologiadeanalisesdesistemas/livro-utilizando-uml-e-padroes-uma-introducao-a-analise-e-ao-projeto-orientados
Link para o livro Utilizando UML e Padrões on-line, no trecho onde fala da habilidade crucial no desenvolvimento OO:
http://books.google.com.br/books?id=ZHtcynS03DIC&pg=PA34&lpg=PA34&dq=habilidade+mais+importante+responsabilidades+craig+larman+utilizando+uml+e+padr%C3%B5es&source=bl&ots=JAa3rHW2ch&sig=DARIxQdi-_UPkgmznD8GIsfJS6w&hl=pt-BR&sa=X&ei=7a22T5uvKZSi8ATnsLmyCg&ved=0CFAQ6AEwAA#v=onepage&q&f=false