Man sollte sich schon vorher Gedanken über den Algorithmus und die zugehörige Datenstruktur machen. Meiner Erfahrung nach sind die Geschwindigkeitsgewinne, die man durch kleinere Optimierungen erreichen kann, meist vernachlässigbar gegen die Verwendung eines besseren Algorithmus.
Davon abgesehen bemühe ich mich in Java besonders darum, in performancekritischen Bereichen auf das unnötige Anlegen/Zerstören von Objekten zu verzichten (re-use).
Meistens ist ja klar, welche Teile besonders oft durchlaufen werden. Dort lohnt Optimierung natürlich am meisten. Oft ist es möglich, gewisse Teile aus diesen oft gerufenen Methoden o.ä. herauszunehmen und vorzuberechnen.